题目描述：

描述一下题目中所给的RSA系统。首先找到两个大整数$P,Q，N=P*Q,$然后令$T=(P-1)*(Q-1)$，令$gcd(E,T)==1$,再搞一个$D$，令$(E*D)$，很明显这个$D$是$E$的逆元。得到公匙${E,N}$，私匙${D,N}$,然后进行加密，$C=M^E$，现在题目给你$C$和${E,N}$，需要你求$M$。

分析： 思路还是比较明确的，通过$N$找到$P,Q$然后求出T，得到4E$，再求$D$最后就可以求出$M$，后面的逆元和$gcd$都不是麻烦事，麻烦的在于找$P,Q$，这题$N$的数据太大，常规的质因子分解无法解决，这里要引入$PollarRho$算法，这个算法的原理很复杂，可能但讲一篇博客都很难讲清楚，这里推荐另一位博主的博客：点击打开链接。

#include<bits/stdc++.h>

using namespace std;
const int MOD=21252;
 
 
long long multi_mod(long long x,long long y,long long c)
{
    x = (x % c + c) % c;
    y = (y % c + c) % c;
 
    long long ans=0;
    while(y){
        if(y&1)ans=ans+x;
        if(ans>=c)ans-=c;
        x=x+x;
        if(x>=c)x-=c;
        y>>=1;
    }
    return ans;
}
long long gcd(long long x,long long y)
{
    return y==0? x:gcd(y,x%y);
}
long long qpow(long long x,long long y,long long MOD)
{
    long long res=1;
    while(y)
    {
        if (y&1) res=multi_mod(res,x,MOD);
        x=multi_mod(x,x,MOD);
        y=y>>1;
    }
    return res;
}
long long PollarRho(long long n,long long c)
{
    srand(time(NULL));
    long long x=rand()%(n-1)+1;
    long long y=x;
    int i=1;
    int k=2;
    while(true)
    {
        i++;
        x=(qpow(x,2,n)+c)%n;
        long long d=gcd(n+y-x,n);
        if (1<d&&d<n) return d;
        if (y==x) return n;
        if (i==k)
        {
            y=x;
            k=k*2;
        }
    }
}
long long extgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里德求逆元。
{
    long long d=a;
    if (b!=0)
    {
        d=extgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else
    {
        x=1;
        y=0;
    }
    return d;
}
 
long long c,e,n;
 
int main()
{
    while(cin>>c>>e>>n)
    {
        long long p=PollarRho(n,10007);
       // cout<<p<<endl;
        long long q=n/p;
        long long t=(p-1)*(q-1);
        long long x0,y0;
        long long d=extgcd(e,t,x0,y0);
        x0=(x0%t+t)%t;
        cout<<qpow(c,x0,n)<<endl;
    }
    return 0;
}