『算法-ACM 竞赛-数学-数论』-P4718 Pollard-Rho 算法 大数分解

P4718 【模板】Pollard-Rho 算法

题目描述
$Miller Rabin 算法是一种高效的质数判断方法。\虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。\
Pollard Rho是一个非常玄学的方式，用于在O(n^{1/4})的期望时间复杂度内计算合数n的某个非平凡因子。\事实上算法导论给出的是O(\sqrt p)，p是n的某个最小因子，满足pp与n/pn/p互质。但是这些都是期望，未必符合实际。\但事实上Pollard Rho算法在实际环境中运行的相当不错。\
这里我们要写一个程序，对于每个数字检验是否是质数，是质数就输出Prime；如果不是质数，输出它最大的质因子是哪个$

输入格式
第一行，TT 代表数据组数（不大于 350350）

以下 TT 行，每行一个整数 nn，保证 1\le n\le 10^{18}1≤n≤10
18
。

输出格式
输出 TT 行。

对于每组测试数据输出结果。

输入输出样例
输入 #1 复制
6
2
13
134
8897
1234567654321
1000000000000
输出 #1 复制
Prime
Prime
67
41
4649
5
这个题目之考察了计算，没考察分解，我博客里有带输出元素的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pr;
ll pmod(ll a, ll b, ll p) { return (a * b - (ll)((long double)a / p * b) * p + p) % p; } //普通的快速乘会T
ll gmod(ll a, ll b, ll p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = pmod(res, a, p);
        a = pmod(a, a, p);
        b >>= 1;
    }
    return res;
}
inline ll gcd(ll a, ll b)
{ //听说二进制算法特快
    if (!a) return b;
    if (!b)return a;
    int t = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    do
    {
        b >>= __builtin_ctzll(b);
        if (a > b)
        {
            ll t = b;
            b = a, a = t;
        }
        b -= a;
    } while (b);
    return a << t;
}
bool Miller_Rabin(ll n)
{
    if (n == 46856248255981ll || n < 2)
        return false; //强伪素数
    if (n == 2 || n == 3 || n == 7 || n == 61 || n == 24251)
        return true;
    if (!(n & 1) || !(n % 3) || !(n % 61) || !(n % 24251))
        return false;
    ll m = n - 1, k = 0;
    while (!(m & 1))
        k++, m >>= 1;
    for (int i = 1; i <= 20; ++i) // 20为Miller-Rabin测试的迭代次数
    {
        ll a = rand() % (n - 1) + 1, x = gmod(a, m, n), y;
        for (int j = 1; j <= k; ++j)
        {
            y = pmod(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)
                return 0;
            x = y;
        }
        if (y != 1)
            return 0;
    }
    return 1;
}
ll Pollard_Rho(ll x)
{
    ll n = 0, m = 0, t = 1, q = 1, c = rand() % (x - 1) + 1;
    for (ll k = 2;; k <<= 1, m = n, q = 1)
    {
        for (ll i = 1; i <= k; ++i)
        {
            n = (pmod(n, n, x) + c) % x;
            q = pmod(q, abs(m - n), x);
        }
        t = gcd(x, q);
        if (t > 1)
            return t;
    }
}
void fid(ll n)
{
    if (n == 1)
        return;
    if (Miller_Rabin(n))
    {
        pr = max(pr, n);
        return;
    }
    ll p = n;
    while (p >= n)
        p = Pollard_Rho(p);
    fid(p);
    fid(n / p);
}
int main()
{
    int T;
    ll n;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld", &n);
        pr = 0;
        fid(n);
        if (pr == n)
            puts("Prime");
        else
            printf("%lld\n", pr);
    }
    return 0;
}