＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstdlib>
＃i nclude <cstring>
#define ll long long
using namespace std;

ll mul_mod(ll x,ll y,ll n)
{
    ll ans=0;
    while (y>0)
    {
        if (y&1) ans+=x;
        if (ans>n) ans-=n;
        x<<=1;
        if (x>n) x-=n;
        y>>=1;
    }
    return ans;
}

ll gcd(ll a1,ll a2)
{
    return a2==0?a1:gcd(a2,a1%a2);
}

ll Abs(ll x) { return x>=0?x:-x; }

ll pollard(ll n)
{
    ll x,d,y,c;
    while (1)
    {
        c=y=x=Abs((ll)rand())%n;
        for (int i=1,k=2;;i++)
        {
            x=mul_mod(x,x,n);
            if (x>c) x-=c;
                else x+=n-c;
            d=gcd(Abs(x-y),n);
            if (d==n) break;
            if (d>1) return d;
            if (i==k) { y=x; k<<=1; }
        }
    }
}

void exgcd(ll a,ll b,ll& x,ll& y)
{
    if (b==0) { x=1,y=0; }
    else { exgcd(b,a%b,y,x); y-=x*(a/b); }
}

ll power(ll a,ll b,ll m)
{
    ll ans=1;
    while (b>0)
    {
        if (b&1) ans=mul_mod(ans,a,m);
        a=mul_mod(a,a,m);
        b>>=1;
    }
    return ans;
}

int main()
{
    ll tep,n,c,e,t,p,q,a,b,x,y,d;
    while (cin>>c>>e>>n)
    {
        tep=pollard(n);
        p=tep-1;
        q=n/tep-1;
        t=p*q;
        a=e,b=t;
        exgcd(a,b,x,y);
        if (x<0) x=(x%t+t)%t;
        d=x;
        cout<<power(c,d,n)<<endl;
    }
    return 0;
}

一、扩展欧几里得算法：

扩展欧几里得算法是exgcd，显然它只是求最大公约数的一个扩展版。

下面先上主函数的代码，再一步一步分析

ll exgcd(ll a,ll b,ll& d,ll& x,ll& y)

{

	if (b==0) { d=a; x=1; y=0; }

	else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }

}

注意 ll表示的是long long或 __int64 

因为一般的int数据范围是不够的。

这个算法的具体证明和实现只要在草稿纸上列出

a1*x1+b1*y1=gcd

a2*x2+b2*y2=gcd

其中gcd为(a1,b1)的最大公约数，由于题目算法过程相当于辗转相除法，所以gcd也是(a2,b2)的最大公约数。

又有a2=b1,b2=a1%b1=a1-a1/b1*b1

代入后即可得 x1,y1,x2,y2 的关系了。

二、Pollard_Roh因数分解。

该算法的主要思想就是不断地随机枚举每一个数来判断该数是否是所求数的因数

如果要判断一个数是否为素数的话，应该设置一个循环上限，使其超过了这个上限就自动退出就可以了，据说这个算法还是比较靠谱的，而且时间开销上十分的优。

贴个代码以示路过：

ll pollard(ll n)

{

	ll x,y,c,d;

	while (1)

	{

		x=y=c=abs((ll)rand())%n;

		for (int i=1,k=2;;i++)

		{

			x=mul_mod(x,x,n);//边乘边取模，否则果断会溢出出错。 

			if (x>c) x-=c;

				else x+=n-c;

			d=gcd(abs(x-y),n);

			if (d==n) break;可能是质数，重新指定x，y进行判断。

				else if (d!=1) return d;//d!=1说明找到了一个因数d，本题可以直接退出函数了。

			if (i==k) { y=x; k<<=1; }//控制x和y的值，这是比较随意的，只要设置合理就行。

		}

	}

}