嘟嘟嘟
这题我读了两遍才懂，然后感觉要解什么高次同余方程……然后我又仔细的看了看题，发现只要求得\(p\)和\(q\)就能求出\(r\)，继而用exgcd求出\(d\)，最后用快速幂求出\(n\)。
再看看这个数据范围，用Pollard-Rho最适合不过了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
//const int maxn = ;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
ll e, N, c, r;
In ll mul(ll a, ll b, ll mod)
{
ll d = ((long double)a / mod * b + 1e-8);
ll r = a * b - d * mod;
return r < 0 ? r + mod : r;
}
In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
In ll f(ll x, ll a, ll mod) {return (mul(x, x, mod) + a) % mod;}
int a[] = {2, 3, 5, 7, 11};
const int M = (1 << 7) - 1;
In ll find(ll n)
{
for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i];
ll x = rand(), y = x, a = rand() % (n - 2) + 2, t = 1;
for(int k = 2;; k <<= 1, y = x)
{
ll p = 1;
for(int i = 1; i <= k; ++i)
{
x = f(x, a, n);
p = mul(p, abs(x - y), n);
if(!(i & M))
{
t = gcd(p, n);
if(t > 1) break;
}
}
if(t > 1 || (t = gcd(p, n)) > 1) break;
}
return t;
}
In ll pollard_rho(ll x)
{
ll p = x;
while(p == x) p = find(x);
return p;
}
In void exgcd(ll a, ll b, ll& x, ll& y, ll& t)
{
if(!b) t = a, x = 1, y = 0;
else exgcd(b, a % b, y, x, t), y -= a / b * x;
}
In ll quickpow(ll a, ll b, ll mod)
{
a %= mod;
ll ret = 1;
for(; b; b >>= 1, a = mul(a, a, mod)) //别忘了这里也会爆long long
if(b & 1) ret = mul(ret, a, mod);
return ret;
}
int main()
{
srand(time(0));
e = read(), N = read(), c = read();
ll p = pollard_rho(N), q = N / p; ll r = (p - 1) * (q - 1);
ll d, y, t;
exgcd(e, r, d, y, t);
t = r / t;
d = (d % t + t) % t;
ll n = quickpow(c, d, N);
write(d), space, write(n), enter;
return 0;
}