Solution:（非常言简意赅）
首先分解出p,q 用Pollard-Rho算法
算出r
解ed≡1(mod r)的同余方程算出d
用快速幂算出cdmod N 然后没啦
Code:
1 #include<bits/stdc++.h> 2 #define Rg register 3 #define go(i,a,b) for(Rg int i=a;i<=b;i++) 4 #define ll long long 5 using namespace std; 6 ll rd() 7 { 8 ll x=0,y=1;char c=getchar(); 9 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 10 while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} 11 return x*y; 12 } 13 ll e,n,c,p,d,g,r; 14 ll mul(ll x,ll y,ll z) 15 { 16 ll sm=0; 17 while(y){if(y&1)sm=(sm+x)%z;x=(x<<1)%z;y>>=1;} 18 return sm; 19 } 20 ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);} 21 ll f(ll x){return (mul(x,x,n)+g)%n;} 22 void Pollard() 23 { 24 ll a,b;g=rand()%n+1;ll t=0; 25 while(!p) 26 { 27 a=b=rand()%n+1,g=rand()%n+1; 28 while(1) 29 { 30 a=f(a);b=f(f(b));if(a==b)break; 31 ll sm=gcd(abs(a-b),n); 32 if(sm>1){p=sm;break;} 33 } 34 } 35 } 36 ll ksm(ll x,ll y) 37 { 38 ll ans=1; 39 while(y) 40 {if(y&1)ans=mul(ans,x,n);x=mul(x,x,n);y>>=1;} 41 return ans; 42 } 43 ll exgcd(ll a,ll b,ll &x,ll &y) 44 { 45 if(!b){x=1;y=0;return a;} 46 ll d=exgcd(b,a%b,y,x); 47 y-=a/b*x;return d; 48 } 49 int main() 50 { 51 srand(time(0)); 52 e=rd(),n=rd(),c=rd();Pollard(); 53 r=(p-1)*(n/p-1);exgcd(e,r,d,g); 54 while(d<0)d+=r;while(d>r)d-=r; 55 printf("%lld %lld",d,ksm(c,d)); 56 return 0; 57 }