[FOJ1759] Super A^B mod C

题目

题目链接。求 A ^ B mod C, B 很大。
 

思路

A ^ B mod C = A ^ {B mod \phi(C) + \phi(C)} mod C , B > \phi(C)。对于小于 \phi(C) 的部分直接使用快速幂,大于的部分用该公式将 B 缩小后用快速幂。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注