## 【BZOJ 4522】[Cqoi2016] 密钥破解

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL e,N,c,r,d,n;

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

inline LL EX_GCD(LL a, LL b) {
LL t1, t2;
EX_GCD(t1,a,t2,b);
return (t1%r + r) % r;
}

inline LL Mul(LL a, LL b) {
LL ret = 0;
while (b) {
if (b&1) ret  = (ret + a) % N;
a = a*2 % N; b >>= 1;
}
return ret;
}

inline LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = Mul(ret, w);
w = Mul(w, w); t >>= 1;
}
return ret;
}

inline LL GCD(LL a, LL b){
while (b) a = a % b, swap(a, b);
return a;
}

inline void Decompose(){
for (int seed=(rand()&32767)%(N-1)+1;!r;seed=(rand()&32767)%(N-1)+1) {
LL w = rand() % (N-1) + 1, seg=2, tmp = -1, cnt = 0, gcd;
while (w != tmp && !r) {
gcd = GCD(abs(w-tmp), N);
if (1 < gcd && gcd < N) r = Mul(N/gcd-1,gcd-1);
if (++cnt == seg) seg <<= 1, tmp = w;
w = (Mul(w,w) + seed) % (N-1) + 1;
}
}
}

int main(){
srand(999971);
cin>>e>>N>>c; Decompose();
d = EX_GCD(e,r); n = pow(c,d);
cout<<d<<' '<<n;
return 0;
}