数学--数论---P4718 Pollard-Rho算法大数分解

P4718 【模板】Pollard-Rho算法

题目描述

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

}

巴特西

数学--数论---P4718 Pollard-Rho算法大数分解

最新文章

热门文章

巴特西

数学--数论---P4718 Pollard-Rho算法 大数分解

最新文章

热门文章

数学--数论---P4718 Pollard-Rho算法大数分解