POJ Numeric

1284. Primitive Roots

给一个奇质数，求它的原根(primitive root)个数，原根定义是，如果整数a是p的原根，说明a^1, a^2 ... a^(p-1) mod p的结果正好是从1到p-1都有

这里用到的是一个定理，如果一个整数有原根，那么它的原根个数是$\phi(\phi(n))$，质数欧拉函数值是质数减1，所以直接求n-1的欧拉函数值即可，这里$\phi(1)=0$

证明是否存在原根的方法如link，可见奇素数一定有原根

这里n的范围是小于65536，所以直接先筛出所有欧拉函数的值，然后返回即可

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> eu(65536, 0);
    for (int i = 2; i < eu.size(); i++) {
        if (eu[i] == 0) {
            for (int j = i; j < eu.size(); j += i) {
                if (eu[j] == 0) eu[j] = j;
                eu[j] -= eu[j] / i;
            }
        }
    }
    int n;
    while (cin >> n) {
        cout << eu[n-1] << '\n';
        if (cin.eof()) break;
    }
}

---

2407. Relatives

给一个整数$n<10^9$，求小于等于n且和n互质的数的个数，输入以0结束

因为范围过大，不能全部求1到n的欧拉函数，所以对每个数单独求解

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        else if (n == 1) {
            cout << "1\n";
            continue;
        }
        int phi = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) phi -= phi / i;
            while (n % i == 0) n /= i;
        }
        if (n > 1) phi -= phi / n;
        cout << phi << '\n';
    }
}