BZOJ4802 欧拉函数

题意

给出一个数 $n$ ,请求出它的欧拉函数 $\varphi(n)$ ,即 $1$ 至 $n$ 中与 $n$ 互素的数的个数
$n\leq 10^{18}$

题解

首先对于某个数 $n$ ,有
$$\varphi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$$
那么我们可以用 Pollard’s Rho 在 $n^{\frac{1}{4}}$ 内将 $n$ 进行素数分解,然后快速求解欧拉函数
然后问题就解决了呗
一道 Pollard’s Rho 模板题

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 107
typedef long long ll;

int top;
ll primes[7] = {3, 5, 7, 11, 19, 23, 61};
ll res[MAX_N];

inline ll mul (ll x, ll y, ll mod) {
    ll tmp = x * y - (ll)((long double)x / mod * y) * mod;
    return tmp < 0 ? tmp + mod : tmp;
}

inline ll add (ll x, ll y, ll mod) {
    return (x + y) % mod;
}

inline ll quick_pow (ll x, ll p, ll mod) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans = mul(ans, x, mod);
        x = mul(x, x, mod);
        p >>= 1;
    }
    return ans;
}

inline bool isPrime (ll p) {
    if (p < 2) return false;
    if (p == 2) return true;
    if (!(p & 1)) return false;
    ll n = p - 1, t = 0;
    while (!(n & 1)) n >>= 1, t++;
    for (int i = 0; i < 7; ++i) {
        if (p == primes[i]) return true;
        ll x = quick_pow(primes[i], n, p), y = x;
        for (int j = 0; j < t; ++j) {
            x = mul(x, x, p);
            if (x == 1 && !(y == 1 || y == p - 1)) return false;
            y = x;
        }
        if (x != 1) return false;
    }
    return true;
}

inline ll pollardrho (ll n, ll c) {
    if (!(n % 2)) return 2;
    if (!(n % 3)) return 3;
    if (!(n % 5)) return 5;
    if (!(n % 7)) return 7;
    ll x = rand() % (n - 1) + 1, y = x, d = 1, q;
    for (int k = 2; ; k <<= 1, y = x, q = 1) {
        for (int i = 1; i <= k; ++i) {
            x = add(mul(x, x, n), c, n);
            q = mul(q, std::abs(y - x), n);
            d = std::__gcd(q, n);
            if (d > 1) break;
        }
        if (d > 1 || std::__gcd(q, n) > 1) break;
    }
    return d;
}

void solve (ll n, ll cnt) {
    if (n == 1) return;
    if (isPrime(n)) {
        res[++top] = n;
        return;
    }
    ll p = n;
    while (p == n) p = pollardrho(n, cnt--);
    while (!(n % p))
        n /= p;
    solve(p, cnt), solve(n, cnt);
}

int main () {
    srand(0x66ccf);
    ll N;
    read(N);
    solve(N, 13579246);
    std::sort(res + 1, res + top + 1);
    top = std::unique(res + 1, res + top + 1) - res - 1;
    ll ans = N;
    for (int i = 1; i <= top; ++i)
        ans = ans / res[i] * (res[i] - 1);
    printf("%lld\n", ans);
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注