一道Pollard Rho模板题。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=8555;
ll a[20]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 61, 24251, 2147483647, 998244353};
ll inf=1ll<<62;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
inline ll mul(ll a,ll b,ll p)
{
    ll x=(ld)a/p*b;
    ll c=1ull*a*b-1ull*x*p;
    return (c+p)%p;
}
inline ll fpow(ll a,ll b,ll p){ll ans=1;for(;b;b>>=1,a=mul(a,a,p))if(b&1)ans=mul(ans,a,p);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;}
ll f(ll x,ll c,ll n){return (mul(x,x,n)+c)%n;}
ll pr(ll n)
{
    ll s=0,t=0,c=rand()%(n-1)+1,val=1;
    for(int i=1;;i<<=1,s=t,val=1)
    {
        for(int j=1;j<=i;j++)
        {
            t=f(t,c,n);
            val=mul(val,abs(t-s),n);
            if(j%127==0)
            {
                ll d=gcd(val,n);
                if(d>1)return d;
            }
        }
        ll d=gcd(val,n);
        if(d>1)return d;
    }
}
int main()
{
    ll e,n,c;qr(e),qr(n),qr(c);
    ll p=n;while(p>=n)p=pr(n);
    ll q=n/p,r=(p-1)*(q-1);
    ll x,y,d;d=exgcd(e,r,x,y);
    x=(x%r+r)%r;qw(x);putchar(' ');
    ll w=fpow(c,x,n);
    qw(w);puts("");
    return 0;
}