φ(7) 是多少
运行下面这段程序:
本节模型:phi(n) 试除出每个质因子 p,答案乘上 (1 - 1/p)。
#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long phi(long long n) {
// 欧拉函数:1..n 里和 n 互质的个数
long long r = n, m = n;
for (long long p = 2; p * p <= m; p++) {
if (m % p == 0) {
while (m % p == 0) m /= p;
r -= r / p;
}
}
if (m > 1) r -= r / m;
return r;
}
int main() {
cout << phi(7) << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论