FZU 1759 Super A^B mod C （欧拉函数，降幂公式）

FZU 1759 Super A^B mod C （欧拉函数，降幂公式）

Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

3 2 42 10 1000

Sample Output

124

思路

一道指数非常可怕的题目，显然快速幂是无法直接求解的，这里我们需要用到降幂。

ABmod C=AB mod ϕ(C)+ϕ(C)mod C ，当且仅当 B>=ϕ(C)

ϕ

AC 代码

#include#include#include#includeusing namespace std;const int maxn = 1e6+10;typedef __int64 LL;LL pr[maxn],a,c;bool prime[maxn];char b[maxn];void getprime() //筛法素数表{ int i,j,k=0; memset(prime,true,sizeof(prime)); for(i=2; i1) rea=rea-rea/n; return rea;}LL mult(LL a,LL b,LL mod){ LL res = 1; a%=mod; while(b) { if(b&1)res = (res*a)%mod; a = (a*a)%mod; b>>=1; } return res;}void solve(){ LL ph = phi(c); a%=c; int len = strlen(b); if(len>LL(log10(ph))) { LL res = 0; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。