- #include<iostream>
- #include<cstdio>
- #include<ctime>
- #include<cstdlib>
- using namespace std;
- __int64 abs(__int64 x)
- {
- return x>0?x:-x;
- }
- __int64 Multi_Mod(__int64 a,__int64 b,__int64 N)
- { //乘法转换为加法实现
- __int64 tmp = 0;
- while(b)
- {
- if(b&1)
- {
- tmp += a;
- tmp%=N;
- }
- a<<=1;
- a%=N;
- b>>=1;
- }
- return tmp;
- }
- __int64 Random() //随机数
- {
- __int64 x;
- x = rand();
- x *= rand();
- x *= rand();
- x *= rand();
- return x;
- }
- __int64 gcd(__int64 a,__int64 b)
- {
- if(b == 0) return a;
- return gcd(b,a%b);
- }
- int PollardRho(__int64 N)
- {
- if(!(N&1)) return 2;
- int i,k;
- while(true)
- {
- __int64 x = abs(Random()%N),y=x;
- __int64 c = abs(Random())%N;
- if(c ==0 || c==2) c = 1;
- for(i=1,k=2;;i++)
- {
- x = Multi_Mod(x,x,N);
- if(x>=c) x-=c;
- else x+=N-c;
- if(x == N) x = 0;
- if(x == 0) x = N-1;
- else x--;
- __int64 d = gcd(x>y?x-y:y-x,N);
- if(d == N) break;
- if(d!=1) return d;
- if(i==k)
- {
- y = x; k<<=1;
- }
- }
- }
- }
- void Extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
- {
- if(b == 0)
- {
- x = 1; y = 0;
- return ;
- }
- Extend_gcd(b,a%b,x,y);
- __int64 tmp = x;
- x = y;
- y = tmp - a/b*y;
- }
- __int64 pow_mod(__int64 a,__int64 b,__int64 N)
- {
- __int64 tmp = 1;
- while(b)
- {
- if(b&1)
- tmp = Multi_Mod(tmp,a,N);
- a = Multi_Mod(a,a,N); //将乘法转换为加法实现,避免溢出
- b>>=1;
- }
- return tmp;
- }
- int main()
- {
- srand((unsigned int)time(NULL));
- __int64 C,E,N,D,P,Q,K,T,M;
- while(scanf("%I64d%I64d%I64d",&C,&E,&N)!=EOF)
- {
- P = PollardRho(N); //求P,Q
- Q = N/P;
- T = (P-1)*(Q-1); // Phi(N)
- Extend_gcd(E,T,D,K); //求解得到D
- D = (D%T+T)%T;
- M = pow_mod(C,D,N); //M = C^D mod N
- printf("%I64d\\n",M);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/081120136975.html
来源: http://www.codesnippet.cn/detail/081120136975.html