「POJ-1284」Primitive Roots-原根+欧拉函数

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <climits>
#include <ctime>
#include <cstdlib>
const int MAXN = 70000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
    mu[1] = phi[1] = 1;
    for (register int i = 2; i <= MAXN; i++) {
        if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
        for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
        }
    }
}
int main() {
    init();
    register int t;
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    while (std::cin >> t) std::cout << phi[t - 1] << "\n";
    return 0;
}