\(\text{Description}\)
定义函数 \(f\)，该函数满足
\[\sum\limits_{d\mid n}f(d)=n \]给定 \(N\) 个正整数 \(A_1,A_2,\dots,A_n\)，请求出 \(\sum_{i=1}^Nf(A_i)\)。
| 测试点编号 | \(N\) | \(A_i\) |
|---|---|---|
| \(0\) | \(100\) | \(\le100\) |
| \(1\) | \(100\) | \(\le100\) |
| \(2\) | \(1000\) | \(\le10000\) |
| \(3\) | \(3\times10^7\) | \(7\) |
| \(4\) | \(3000\) | \(\le10^6\) |
| \(5\) | \(4000\) | \(\le10^6\) |
| \(6\) | \(10000\) | \(\le10^7\) |
| \(7\) | \(100000\) | \(\le10^7\) |
| \(8\) | \(5\) | \(162614600673829,1125897758834689,222915410844073,18004502351257601,2001600073928249\) |
| \(9\) | \(3\) | \(18014398241046527,18014398777917439,489133282872437279\) |
\(\text{Solution}\)
对于测试点 \(3,8,9\)，直接变成提交答案（
\(3:ans=3\times10^7\times(7-1)=1.8\times10^8\)
\(8:\) 所有数都是质数 \(\times\) 质数。
\(9:\) 所有数都是质数。
对于剩下的有 \(3\) 种思路：
\(1.\)
\(\begin{aligned}n&=\sum_{d\mid n}f(d)\\&=\sum_{d\mid n,d\ne n}f(d)+f(n)\end{aligned}\)
\[\therefore f(n)=n-\sum\limits_{d\mid n,d\ne n}f(d) \]这个可以用埃氏筛。
时间复杂度约 \(\mathcal{O}(值域\log\log值域)\)。
前置芝士：欧拉函数
\(1\sim n\) 中与 \(n\) 互质的数的个数记为 \(\varphi(n)\)，它被称为欧拉函数。
以下是一些要用到的性质：
- 若 \(n\) 的质因数分解为 \(n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}\)，则 \(\varphi(n)=n\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\cdots\times\frac{p_m-1}{p_m}\) （欧拉公式）。
证明：
每 \(p_1\) 个数中有 \((p_1-1)\) 个与 \(n\) 互质，这其中每 \(p_2\) 个数中有 \((p_2-1)\) 个与 \(n\) 互质……
- 若 \(\gcd(n,m)=1\)，则 \(\varphi(nm)=\varphi(n)\varphi(m)\)（\(\varphi(n)\) 是积性函数，但不是完全积性函数）。
证明：
\(n\) 和 \(\frac{n}{p}\) 的分解中都含 \(p\)，只是 \(p\) 的次数不同。\(\varphi(n)=n\times\frac{p-1}{p}\times A,\varphi(\frac{n}{p})=\frac{n}{p}\times\frac{p-1}{p}\times A\)，那么 \(\varphi(n)\div\varphi(\frac{n}{p})=p\)。
- 若 \(p\) 为质数且 \(p\mid n,p^2\mid n\)，则 \(\varphi(n)=\varphi(\frac{n}{p})p\)。
证明：
\(\varphi(n)=n\times\frac{p-1}{p}\times A,\varphi(\frac{n}{p})=\frac{n}{p}\times A\)，那么 \(\varphi(n)\div\varphi(\frac{n}{p})=p-1\)。
- 若 \(p\) 为质数且 \(p\mid n,p^2\nmid n\)，则 \(\varphi(n)=\varphi(\frac{n}{p})(p-1)\)。
证明：
\(\varphi(n)=n\times\frac{p-1}{p}\times A,\varphi(\frac{n}{p})=\frac{n}{p}\times A\)，那么 \(\varphi(n)\div\varphi(\frac{n}{p})=p-1\)。
- \(\sum\limits_{d\mid n}\varphi(d)=n\)。
证明：
设 \(g(n)=\sum\limits_{d\mid n}\varphi(n)\)，因为 \(\varphi(n)\) 是积性函数，所以有 \(g(nm)=\sum\limits_{d\mid nm}\varphi(d)=\sum\limits_{d\mid n}\varphi(d)\sum\limits_{d\mid m}\varphi(d)=g(n)g(m)\)，即 \(g(n)=\sum\limits_{d\mid n}\varphi(n)\) 是积性函数。
以单个质因数 \(p\) 为例，若次数是 \(k\)，则
\(\begin{aligned}g(p^m)&=1+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^k)\\&=1+\varphi(p)+\varphi(p)\times p+\cdots+\varphi(p)\times p^{k-1}\\&=1+\varphi(p)\times \frac{p^{k}}{p-1}=1+(p-1)\frac{p^k-1}{p-1}\\&=p^k\end{aligned}\)
以 \(n=2^3\times3^2\) 为例，
\(\begin{aligned}g(n)&=\varphi(1)+\varphi(2)+\varphi(2^2)+\varphi(2^3)+\varphi(3)+\varphi(3^2)+\varphi(2\times3)+\varphi(2^2\times3)+\varphi(2^3\times3)+\varphi(2\times3^2)+\varphi(2^2\times3^2)+\varphi(2^3\times3^2)\\&=1+\varphi(2)+\varphi(2^2)+\varphi(2^3)+\varphi(3)+\varphi(3^2)+\varphi(2)\times\varphi(3)+\varphi(2^2)\times\varphi(3)+\varphi(2^3)\times\varphi(3)+\varphi(2)\times\varphi(3^2)+\varphi(2^2)\times\varphi(3^2)+\varphi(2^3)\times\varphi(3^2)\\&=1\times(1+\varphi(3)+\varphi(3^2))+\varphi(2)\times(1+\varphi(3)+\varphi(3^2))+\varphi(2^2)\times(1+\varphi(3)+\varphi(3^2))+\varphi(2^3)\times(1+\varphi(3)+\varphi(3^2))\\&=(1+\varphi(2)+\varphi(2^2))\times(1+\varphi(3)+\varphi(3^2))\\&=g(2^2)\times g(3^2)\\&=2^3\times3^2\\&=n\end{aligned}\)
即
\(\begin{aligned}g(n)&=\prod\limits_{i=1}^m g(p_i^{c_i})\\&=\prod\limits_{i=1}^m p_i^{c_i}\\&=n\end{aligned}\)
\(\therefore\sum\limits_{d\mid n}\varphi(d)=n.\)
既然 \(\varphi(n)\) 有性质 \(5\)，而 \(f\) 有 \(\sum\limits_{d\mid n}f(d)=n\)，那么可以直接将 \(f(n)\) 视为 \(\varphi(n)\)。
得出的答案一定是一样的，但是这可能不严谨。
不过可以搞出 \(\mathcal{O}(值域)\) 的做法（
\(2.\)
利用性质 \(1\) 可以单个 \(\mathcal{O}(\sqrt{n})\) 计算 \(f(n)=\varphi(n)\)。
时间复杂度为 \(\mathcal{O}(n\sqrt{值域})\)。
\(3.\)
利用性质 \(3,4\)，我们可以使用线性筛。
在代码
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
f[i] = i - 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
break;
}
}
}
中，当 i % p[j] == 0 时，\(p_j\mid(i\times p_j)\) 且 \(p_j^2\mid(i\times p_j)\)。
根据性质 \(3\)，有 \(\varphi(i\times p_j)=\varphi(i)p_j\)。
在 \(if\) 下面，\(p_j\mid(i\times p_j)\) 且 \(p_j^2\nmid(i\times p_j)\)。
根据性质 \(4\)，有 \(\varphi(i\times p_j)=\varphi(i)(p_j-1)\)。
时间复杂度为 \(\mathcal{O}(值域)\)。
\(res:\)
\(1:1000ms\)
\(2:604ms\)
\(3:156ms\)
\(\text{Code}\)
注意数组开 long long 会 \(\rm MLE\)，只能把 \(ans\) 开成 long long。
\(1.\)
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e7 + 5;
int f[MAXN], a[MAXN];
void pre(int n)
{
f[1] = 1;
for (int i = 2; i <= n; i++)
{
f[i] = i - 1;
}
for (int i = 2; i <= n; i++)
{
for (int j = 2; j <= i && j * i <= n; j++)
{
if (j == i)
{
f[i * j] -= f[i];
}
else
{
f[i * j] -= (f[i] + f[j]);
}
}
}
}
int main()
{
int n;
scanf("%d", &n);
if (n == 30000000)
{
puts("180000000");
return 0;
}
else if (n == 5)
{
puts("21517525747423580");
return 0;
}
else if (n == 3)
{
puts("525162079891401242");
return 0;
}
pre(MAXN - 2);
long long ans = 0ll;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
ans += (long long)f[x];
}
printf("%lld\n", ans);
return 0;
}
\(2.\)
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int MAXN = 1e7 + 5;
int phi(int n)
{
int res = n;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
res = res / i * (i - 1);
while (n % i == 0)
{
n /= i;
}
}
}
if (n != 1)
{
res = res / n * (n - 1);
}
return res;
}
signed main()
{
int n;
scanf("%lld", &n);
if (n == 30000000)
{
puts("180000000");
return 0;
}
else if (n == 5)
{
puts("21517525747423580");
return 0;
}
else if (n == 3)
{
puts("525162079891401242");
return 0;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
ans += phi(x);
}
printf("%lld\n", ans);
return 0;
}
\(3.\)
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e7 + 5;
int a[MAXN], p[MAXN], f[MAXN];
bool vis[MAXN];
void pre(int n)
{
f[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
f[i] = i - 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
f[i * p[j]] = f[i] * p[j];
break;
}
f[i * p[j]] = f[i] * (p[j] - 1);
}
}
}
int main()
{
int n;
scanf("%d", &n);
if (n == 30000000)
{
puts("180000000");
return 0;
}
else if (n == 5)
{
puts("21517525747423580");
return 0;
}
else if (n == 3)
{
puts("525162079891401242");
return 0;
}
pre(MAXN - 2);
long long ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
ans += (long long)f[x];
}
printf("%lld\n", ans);
return 0;
}