Luogu4358 [CQOI2016]密钥破解

题目链接：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;
}