题目链接:Link
题解
其实就是一个Pollard-Rho的板子题,但是Luogu上的【模板】Pollard-Rho算法 难度是道黑题,然后这道是个紫题。
这个题就是把它告诉你的流程算一遍就可以了。
做法很显然,那个p, q的计算显然非常的简单,直接Pollard-Rho把N分解了就是。
$p,q$出来了,$r$直接按照$(p - 1)(q - 1) $ 算就可以了。
这个时候,它给了你一个同余方程, ed \equiv 1\pmod {r} ,知道了1, r,所以直接扩欧求解即可。
然后最后快速幂求n
但是注意2^{64} * 2 ^ {64} 是肯定会炸 long long 的,所以要么就用__int128或者快速乘了
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read()
{
char ch = getchar();
LL f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
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;
inline LL Qmul(LL a, LL b, LL p)
{
LL d = (long double) a / p * b + 1e-8;
LL r = a * b - d * p;
return r < 0 ? r + p : r;
}
inline LL Qpow(LL x, LL y, LL p)
{
LL ans = 1;
for ( ; y ; x = Qmul(x, x, p), y >>= 1) y & 1 ? ans = Qmul(ans, x, p) : 0;
return (LL) ans % p ;
}
inline LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
inline LL f(LL x, LL a, LL mod) {return (Qmul(x, x, mod) + a) % mod;}
int a[] = {2, 3, 5, 7, 11};
const int M = (1 << 7) - 1;
inline 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 = Qmul(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;
}
inline LL pollard_rho(LL x)
{
LL p = x;
while (p == x) p = find(x);
return p;
}
inline 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;
}
int main()
{
srand(time(NULL));
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 = Qpow(c, d, N);
std::cout << d << " " << n;
return 0;
}
Comments | NOTHING