题目地址：BZOJ：Problem 4802. — 欧拉函数

题目描述

已知N，求phi(N)

输入输出格式

输入格式：
正整数N。N<=10^18

输出格式：
输出phi(N)

输入输出样例

输入样例#1：

8

输出样例#1：

4

题解

本题需要的数学姿势有：Miller-Rabin素性测试与Pollard’s rho算法 | KSkun’s Blog
我们知道欧拉函数有一种求法是
\varphi(x) = x (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})
那分解一波质因数就可以求了。数据范围让我们用PR算法。
吐槽：std::abs被卡常了

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL mul(LL a, LL b, LL p) {
    a %= p; b %= p;
    LL res = 0;
    while(b) {
        if(b & 1) {
            res += a; res %= p;
        }
        a <<= 1;
        if(a >= p) a %= p;
        b >>= 1;
    }
    return res;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1;
    for(; k; n = mul(n, n, p), k >>= 1) {
        if(k & 1) res = mul(res, n, p);
    }
    return res;
}

LL T, n;

inline bool miller_rabin(LL x) {
    if(x == 2) return true;
    LL t = x - 1, cnt2 = 0;
    while(!(t & 1)) {
        t >>= 1; cnt2++;
    }
    for(int i = 0; i < 20; i++) {
        LL a = rand() % (x - 2) + 2, now, lst;
        now = lst = fpow(a, t, x);
        for(int j = 1; j <= cnt2; j++) {
            now = mul(lst, lst, x);
            if(now == 1 && lst != 1 && lst != x - 1) return false;
            lst = now;
        }
        if(now != 1) return false;
    }
    return true;
}

LL mn;

inline LL gcd(LL a, LL b) {
    if(a == 0) return 1;
    while(b) {
        LL t = a % b; a = b; b = t;
    }
    return a;
}

inline LL abs(LL x) {
    return x < 0 ? -x : x;
}

inline LL pollard_rho(LL x, LL k) {
    LL a = rand() % (x - 1) + 1, b = a, t1 = 1, t2 = 2;
    for(;;) {
        t1++;
        a = (mul(a, a, x) + k) % x;
        LL g = gcd(abs(b - a), x);
        if(g > 1 && g < x) return g;
        if(b == a) return x;
        if(t1 == t2) {
            b = a;
            t2 <<= 1;
        }
    }
}

std::vector<LL> divi;

inline void caldivisor(LL x) {
    if(x == 1) return;
    if(miller_rabin(x)) {
        divi.push_back(x);
        return;
    }
    LL p = x;
    while(p >= x) p = pollard_rho(x, rand() % (x - 1) + 1);
    caldivisor(p);
    caldivisor(x / p);
}

LL N;

int main() {
    srand(time(NULL));
    N = readint();
    if(N == 1) {
        puts("1"); return 0;
    }
    if(miller_rabin(N)) {
        printf("%lld", N - 1); return 0;
    }
    caldivisor(N);
    std::sort(divi.begin(), divi.end());
    divi.erase(std::unique(divi.begin(), divi.end()), divi.end());
    LL phi = N;
    for(int i = 0; i < divi.size(); i++) {
        phi /= divi[i];
        phi *= divi[i] - 1;
    }
    printf("%lld", phi);
    return 0;
}