板题…没啥说的…
求逆元出来后如果是负的记得加回正数
CODE
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
queue<int>arr;
inline LL multi(LL a, LL b, LL p) { //快速乘
LL re = a * b - (LL)((long double) a / p * b + 1e-8) * p;
return re < 0 ? re + p : re;
}
LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }
inline LL qpow(LL a, LL b, LL p) {
LL re = 1;
while(b) {
if(b&1) re = multi(re, a, p);
a = multi(a, a, p); b >>= 1;
}
return re;
}
inline LL Pollard_Rho(LL n, int sed) {
LL i = 1, k = 2, x = rand()%(n-1)+1, y = x;
while(true) {
x = (multi(x, x, n) + sed) % n;
LL p = gcd(n, (y-x+n)%n);
if(p != 1 && p != n) return p;
if(y == x) return n;
if(++i == k) y = x, k <<= 1;
}
}
LL x[100];
inline bool MR(LL n) {
if(n == 2) return 1;
int s = 20, t = 0; LL u = n-1;
while(!(u&1)) ++t, u>>=1;
while(s--) {
LL a = rand()%(n-2) + 2;
x[0] = qpow(a, u, n);
for(int i = 1; i <= t; ++i) {
x[i] = multi(x[i-1], x[i-1], n);
if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return 0;
}
if(x[t] != 1) return 0;
}
return 1;
}
void find(LL n, int sed) {
if(n == 1) return;
if(MR(n)) { arr.push(n); return; }
LL p = n; int k = sed;
while(p == n) p = Pollard_Rho(p, sed--);
find(p, k);
find(n/p, k);
}
LL p, q, e, d, N, c, tmp, Z;
void exgcd(LL a, LL b, LL &x, LL &y, LL &Z) {
if(!b) { x = 1; y = 0; Z = a; return; }
exgcd(b, a%b, y, x, Z); y -= x*(a/b);
}
int main()
{
srand(19260817);
scanf("%lld%lld%lld", &e, &N, &c);
find(N, 107);
p = arr.front(), arr.pop();
q = arr.front(), arr.pop();
exgcd(e, (p-1)*(q-1), d, tmp, Z);
Z = (p-1)*(q-1)/Z;
d = (d % Z + Z) % Z;
printf("%lld %lld\n", d, qpow(c, d, N));
}