欧拉函数的定义
\(1\) ~ \(N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\phi(N)\)。
若在算数基本定理中，\(N=p_1^{a_1}p_2^{a_2}...p_{m}^{a_m}\)，则：
\(\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times...\times\frac{p_m-1}{p_m}\)
把 \(\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times...\times\frac{p_m-1}{p_m}\) 式子展开会发现变成了容斥原理，所以是对的。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a;
int main()
{
cin >> n;
while (n--) {
cin >> a;
long long ans = a;
for (int i = 2; i <= a / i; ++i) {
if (a % i == 0) {
ans = ans * (i - 1) / i;
while (a % i == 0) a /= i;
}
}
if (a > 1) ans = ans * (a - 1) / a;
printf("%lld\n", ans);
}
return 0;
}
欧拉函数的定义
\(1\) ~ \(N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\phi(N)\)。
若在算数基本定理中，\(N=p_1^{a_1}p_2^{a_2}...p_{m}^{a_m}\)，则：
\(\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times...\times\frac{p_m-1}{p_m}\)
分类讨论一下：
- 如果 \(i\) 是质数那么 \(\phi(i)=i-1\)
- 如果 \(i\) 是合数，我们得用线性筛了。
- \(pj \mid i\) 时，我们只需要将基数项 \(N\) 乘上 \(pj\) 就行了，\(\phi(pj\times i)=phi(i)\times pj\)
- \(pj \nmid i\) 时，我们要把基数项 \(N\) 乘上 \(pj\) 还得补上 \(\frac{pj-1}{pj}\)，化简之后变为 \(\phi(pj\times i)=phi(i)\times(pj-1)\)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 10;
typedef long long ll;
int phi[MAXN], primes[MAXN], n, cnt;
bool st[MAXN];
ll get(int n) {
phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!st[i]) {
primes[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; ++j) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
ans += phi[i];
return ans;
}
int main() {
cin >> n;
cout << get(n);
return 0;
}