BZOJ4802 欧拉函数 （Pollard-Rho Miller-Robin）

题目

求大数的欧拉函数φ\varphiφ

题解

Pollard-Rho 板子

CODE

#pragma GCC optimize (3)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

inline LL mul(LL a, LL b, LL p) {

    a=(a%p+p)%p, b=(b%p+p)%p;

    return (((a*b)-(LL)((long double)a*b/p)*p)%p+p)%p;

}

inline LL qpow(LL a, LL b, LL p) {

    LL re=1;

    for(; b; b>>=1, a=mul(a,a,p))

        if(b&1) re=mul(re,a,p);

    return re;

}

namespace Pollard_Rho {

    int bs[5] = { 2, 3, 7, 31, 61 };

    bool Miller_Robin(LL x) {

        for(int i = 0; i < 5; ++i) if(x == bs[i]) return 1;

        LL res = x-1, k = 0;

        for(; !(res&1); res>>=1, ++k);

        for(int i = 0; i < 5; ++i) {

            LL pre = qpow(bs[i], res, x), now;

            for(int t = k; t--; swap(now, pre))

                if((now=mul(pre, pre, x)) == 1 && pre != 1 && pre != x-1)

                    return 0;

            if(pre != 1) return 0;

        }

        return 1;

    }

    LL Rho(LL x, LL c) {

        LL i = 1, j = 0, sum = 1, a = rand()%(x-1) + 1, b = a, d = 1;

        while(d == 1) {

            sum = mul(sum, abs((a=(mul(a,a,x)+c)%x)-b), x);

            if(++j == i) i<<=1, b = a, d = __gcd(sum, x);

            if(!(j&1023)) d = __gcd(sum, x);

        }

        return d == x ? Rho(x, c+1) : d;

    }

    map<LL, int>mp;

    map<LL, int>::iterator it;

    void Pollard(LL x) {

        if(x == 1) return;

        if(Miller_Robin(x)) { ++mp[x]; return; }

        LL tmp = Rho(x, 3);

        Pollard(tmp), Pollard(x/tmp);

    }

    vector<pair<LL,int> > Solve(LL x) {

        mp.clear(); Pollard(x);

        vector<pair<LL,int> > re;

        for(it = mp.begin(); it != mp.end(); ++it)

            re.push_back(make_pair(it->first, it->second));

        return re;

    }

}

LL n;

vector<pair<LL,int> >vec;

int main() {

    srand(19260817);

    scanf("%lld", &n);

    vec = Pollard_Rho::Solve(n);

    for(int i = vec.size()-1; i >= 0; --i)

        n = n / vec[i].first * (vec[i].first-1);

    printf("%lld\n", n);

}