定义函数 f f f，该函数满足
∑ d ∣ n f ( d ) = n sumlimits_{dmid n}f(d)=n d∣n∑f(d)=n
给定 N N N 个正整数 A 1 , A 2 , … , A n A_1,A_2,dots,A_n A1,A2,…,An，请求出 ∑ i = 1 N f ( A i ) sum_{i=1}^Nf(A_i) ∑i=1Nf(Ai)。
| 测试点编号 | N N N | A i A_i Ai |
|---|---|---|
| 0 0 0 | 100 100 100 | ≤ 100 le100 ≤100 |
| 1 1 1 | 100 100 100 | ≤ 100 le100 ≤100 |
| 2 2 2 | 1000 1000 1000 | ≤ 10000 le10000 ≤10000 |
| 3 3 3 | 3 × 1 0 7 3times10^7 3×107 | 7 7 7 |
| 4 4 4 | 3000 3000 3000 | ≤ 1 0 6 le10^6 ≤106 |
| 5 5 5 | 4000 4000 4000 | ≤ 1 0 6 le10^6 ≤106 |
| 6 6 6 | 10000 10000 10000 | ≤ 1 0 7 le10^7 ≤107 |
| 7 7 7 | 100000 100000 100000 | ≤ 1 0 7 le10^7 ≤107 |
| 8 8 8 | 5 5 5 | 162614600673829 , 1125897758834689 , 222915410844073 , 18004502351257601 , 2001600073928249 162614600673829,1125897758834689,222915410844073,18004502351257601,2001600073928249 162614600673829,1125897758834689,222915410844073,18004502351257601,2001600073928249 |
| 9 9 9 | 3 3 3 | 18014398241046527 , 18014398777917439 , 489133282872437279 18014398241046527,18014398777917439,489133282872437279 18014398241046527,18014398777917439,489133282872437279 |
对于测试点 3 , 8 , 9 3,8,9 3,8,9，直接变成提交答案（
3 : a n s = 3 × 1 0 7 × ( 7 − 1 ) = 1.8 × 1 0 8 3:ans=3times10^7times(7-1)=1.8times10^8 3:ans=3×107×(7−1)=1.8×108
8 : 8: 8: 所有数都是质数 × times × 质数。
9 : 9: 9: 所有数都是质数。
对于剩下的有 3 3 3 种思路：
1. 1. 1.n = ∑ d ∣ n f ( d ) = ∑ d ∣ n , d ≠ n f ( d ) + f ( n ) begin{aligned}n&=sum_{dmid n}f(d)\&=sum_{dmid n,dne n}f(d)+f(n)end{aligned} n=d∣n∑f(d)=d∣n,d=n∑f(d)+f(n)
∴ f ( n ) = n − ∑ d ∣ n , d ≠ n f ( d ) therefore f(n)=n-sumlimits_{dmid n,dne n}f(d) ∴f(n)=n−d∣n,d=n∑f(d)
这个可以用埃氏筛。
时间复杂度 O ( 值 域 值 域 ) mathcal{O}(值域sqrt{值域}) O(值域值域 )。
前置芝士：欧拉函数1 ∼ n 1sim n 1∼n 中与 n n n 互质的数的个数记为 φ ( n ) varphi(n) φ(n)，它被称为欧拉函数。
以下是一些要用到的性质：
- 若 n n n 的质因数分解为 n = p 1 c 1 p 2 c 2 ⋯ p m c m n=p_1^{c_1}p_2^{c_2}cdots p_m^{c_m} n=p1c1p2c2⋯pmcm，则 φ ( n ) = n × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p m − 1 p m varphi(n)=ntimesfrac{p_1-1}{p_1}timesfrac{p_2-1}{p_2}timescdotstimesfrac{p_m-1}{p_m} φ(n)=n×p1p1−1×p2p2−1×⋯×pmpm−1 （欧拉公式）。
证明：
每 p 1 p_1 p1 个数中有 ( p 1 − 1 ) (p_1-1) (p1−1) 个与 n n n 互质，这其中每 p 2 p_2 p2 个数中有 ( p 2 − 1 ) (p_2-1) (p2−1) 个与 n n n 互质……
- 若 gcd ( n , m ) = 1 gcd(n,m)=1 gcd(n,m)=1，则 φ ( n m ) = φ ( n ) φ ( m ) varphi(nm)=varphi(n)varphi(m) φ(nm)=φ(n)φ(m)（ φ ( n ) varphi(n) φ(n) 是积性函数，但不是完全积性函数）。
证明：
n n n 和 n p frac{n}{p} pn 的分解中都含 p p p，只是 p p p 的次数不同。 φ ( n ) = n × p − 1 p × A , φ ( n p ) = n p × p − 1 p × A varphi(n)=ntimesfrac{p-1}{p}times A,varphi(frac{n}{p})=frac{n}{p}timesfrac{p-1}{p}times A φ(n)=n×pp−1×A,φ(pn)=pn×pp−1×A，那么 φ ( n ) ÷ φ ( n p ) = p varphi(n)divvarphi(frac{n}{p})=p φ(n)÷φ(pn)=p。
- 若 p p p 为质数且 p ∣ n , p 2 ∣ n pmid n,p^2mid n p∣n,p2∣n，则 φ ( n ) = φ ( n p ) p varphi(n)=varphi(frac{n}{p})p φ(n)=φ(pn)p。
证明：
φ ( n ) = n × p − 1 p × A , φ ( n p ) = n p × A varphi(n)=ntimesfrac{p-1}{p}times A,varphi(frac{n}{p})=frac{n}{p}times A φ(n)=n×pp−1×A,φ(pn)=pn×A，那么 φ ( n ) ÷ φ ( n p ) = p − 1 varphi(n)divvarphi(frac{n}{p})=p-1 φ(n)÷φ(pn)=p−1。
- 若 p p p 为质数且 p ∣ n , p 2 ∤ n pmid n,p^2nmid n p∣n,p2∤n，则 φ ( n ) = φ ( n p ) ( p − 1 ) varphi(n)=varphi(frac{n}{p})(p-1) φ(n)=φ(pn)(p−1)。
证明：
φ ( n ) = n × p − 1 p × A , φ ( n p ) = n p × A varphi(n)=ntimesfrac{p-1}{p}times A,varphi(frac{n}{p})=frac{n}{p}times A φ(n)=n×pp−1×A,φ(pn)=pn×A，那么 φ ( n ) ÷ φ ( n p ) = p − 1 varphi(n)divvarphi(frac{n}{p})=p-1 φ(n)÷φ(pn)=p−1。
- ∑ d ∣ n φ ( d ) = n sumlimits_{dmid n}varphi(d)=n d∣n∑φ(d)=n。
证明：
设 g ( n ) = ∑ d ∣ n φ ( n ) g(n)=sumlimits_{dmid n}varphi(n) g(n)=d∣n∑φ(n)，因为 φ ( n ) varphi(n) φ(n) 是积性函数，所以有 g ( n m ) = ∑ d ∣ n m φ ( d ) = ∑ d ∣ n φ ( d ) ∑ d ∣ m φ ( d ) = g ( n ) g ( m ) g(nm)=sumlimits_{dmid nm}varphi(d)=sumlimits_{dmid n}varphi(d)sumlimits_{dmid m}varphi(d)=g(n)g(m) g(nm)=d∣nm∑φ(d)=d∣n∑φ(d)d∣m∑φ(d)=g(n)g(m)，即 g ( n ) = ∑ d ∣ n φ ( n ) g(n)=sumlimits_{dmid n}varphi(n) g(n)=d∣n∑φ(n) 是积性函数。
以单个质因数 p p p 为例，若次数是 k k k，则
g ( p m ) = 1 + φ ( p ) + φ ( p 2 ) + ⋯ + φ ( p k ) = 1 + φ ( p ) + φ ( p ) × p + ⋯ + φ ( p ) × p k − 1 = 1 + φ ( p ) × p k p − 1 = 1 + ( p − 1 ) p k − 1 p − 1 = 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^kend{aligned} g(pm)=1+φ(p)+φ(p2)+⋯+φ(pk)=1+φ(p)+φ(p)×p+⋯+φ(p)×pk−1=1+φ(p)×p−1pk=1+(p−1)p−1pk−1=pk
以 n = 2 3 × 3 2 n=2^3times3^2 n=23×32 为例，
g ( n ) = φ ( 1 ) + φ ( 2 ) + φ ( 2 2 ) + φ ( 2 3 ) + φ ( 3 ) + φ ( 3 2 ) + φ ( 2 × 3 ) + φ ( 2 2 × 3 ) + φ ( 2 3 × 3 ) + φ ( 2 × 3 2 ) + φ ( 2 2 × 3 2 ) + φ ( 2 3 × 3 2 ) = 1 + φ ( 2 ) + φ ( 2 2 ) + φ ( 2 3 ) + φ ( 3 ) + φ ( 3 2 ) + φ ( 2 ) × φ ( 3 ) + φ ( 2 2 ) × φ ( 3 ) + φ ( 2 3 ) × φ ( 3 ) + φ ( 2 ) × φ ( 3 2 ) + φ ( 2 2 ) × φ ( 3 2 ) + φ ( 2 3 ) × φ ( 3 2 ) = 1 × ( 1 + φ ( 3 ) + φ ( 3 2 ) ) + φ ( 2 ) × ( 1 + φ ( 3 ) + φ ( 3 2 ) ) + φ ( 2 2 ) × ( 1 + φ ( 3 ) + φ ( 3 2 ) ) + φ ( 2 3 ) × ( 1 + φ ( 3 ) + φ ( 3 2 ) ) = ( 1 + φ ( 2 ) + φ ( 2 2 ) ) × ( 1 + φ ( 3 ) + φ ( 3 2 ) ) = g ( 2 2 ) × g ( 3 2 ) = 2 3 × 3 2 = n begin{aligned}g(n)&=varphi(1)+varphi(2)+varphi(2^2)+varphi(2^3)+varphi(3)+varphi(3^2)+varphi(2times3)+varphi(2^2times3)+varphi(2^3times3)+varphi(2times3^2)+varphi(2^2times3^2)+varphi(2^3times3^2)\&=1+varphi(2)+varphi(2^2)+varphi(2^3)+varphi(3)+varphi(3^2)+varphi(2)timesvarphi(3)+varphi(2^2)timesvarphi(3)+varphi(2^3)timesvarphi(3)+varphi(2)timesvarphi(3^2)+varphi(2^2)timesvarphi(3^2)+varphi(2^3)timesvarphi(3^2)\&=1times(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^3times3^2\&=nend{aligned} g(n)=φ(1)+φ(2)+φ(22)+φ(23)+φ(3)+φ(32)+φ(2×3)+φ(22×3)+φ(23×3)+φ(2×32)+φ(22×32)+φ(23×32)=1+φ(2)+φ(22)+φ(23)+φ(3)+φ(32)+φ(2)×φ(3)+φ(22)×φ(3)+φ(23)×φ(3)+φ(2)×φ(32)+φ(22)×φ(32)+φ(23)×φ(32)=1×(1+φ(3)+φ(32))+φ(2)×(1+φ(3)+φ(32))+φ(22)×(1+φ(3)+φ(32))+φ(23)×(1+φ(3)+φ(32))=(1+φ(2)+φ(22))×(1+φ(3)+φ(32))=g(22)×g(32)=23×32=n
即
g ( n ) = ∏ i = 1 m g ( p i c i ) = ∏ i = 1 m p i c i = n begin{aligned}g(n)&=prodlimits_{i=1}^m g(p_i^{c_i})\&=prodlimits_{i=1}^m p_i^{c_i}\&=nend{aligned} g(n)=i=1∏mg(pici)=i=1∏mpici=n
∴ ∑ d ∣ n φ ( d ) = n . thereforesumlimits_{dmid n}varphi(d)=n. ∴d∣n∑φ(d)=n.
既然 φ ( n ) varphi(n) φ(n) 有性质 5 5 5，而 f f f 有 ∑ d ∣ n f ( d ) = n sumlimits_{dmid n}f(d)=n d∣n∑f(d)=n，那么可以直接将 f ( n ) f(n) f(n) 视为 φ ( n ) varphi(n) φ(n)。
得出的答案一定是一样的，但是这可能不严谨。
不过可以搞出 O ( 值 域 ) mathcal{O}(值域) O(值域) 的做法（
2. 2. 2.利用性质 1 1 1 可以单个 O ( n ) mathcal{O}(sqrt{n}) O(n ) 计算 f ( n ) = φ ( n ) f(n)=varphi(n) f(n)=φ(n)。
时间复杂度为 O ( n 值 域 ) mathcal{O}(nsqrt{值域}) O(n值域 )。
3. 3. 3.利用性质 3 , 4 3,4 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 ∣ ( i × p j ) p_jmid(itimes p_j) pj∣(i×pj) 且 p j 2 ∣ ( i × p j ) p_j^2mid(itimes p_j) pj2∣(i×pj)。
根据性质 3 3 3，有 φ ( i × p j ) = φ ( i ) p j varphi(itimes p_j)=varphi(i)p_j φ(i×pj)=φ(i)pj。
在 i f if if 下面， p j ∣ ( i × p j ) p_jmid(itimes p_j) pj∣(i×pj) 且 p j 2 ∤ ( i × p j ) p_j^2nmid(itimes p_j) pj2∤(i×pj)。
根据性质 4 4 4，有 φ ( i × p j ) = φ ( i ) ( p j − 1 ) varphi(itimes p_j)=varphi(i)(p_j-1) φ(i×pj)=φ(i)(pj−1)。
时间复杂度为 O ( 值 域 ) mathcal{O}(值域) O(值域)。
r e s : res: res:
1 : 1000 m s 1:1000ms 1:1000ms
2 : 604 m s 2:604ms 2:604ms
3 : 156 m s 3:156ms 3:156ms
Code text{Code} Code注意数组开 long long 会 M L E rm MLE MLE，只能把 a n s ans ans 开成 long long。
1. 1. 1.#include2. 2. 2.#include 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("%lldn", ans); return 0; }
#include3. 3. 3.#include #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("%lldn", ans); return 0; }
#include#include 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("%lldn", ans); return 0; }
