HDU 6428 Problem C. Calculate 莫反+积性函数+线性筛

线性筛"/>

HDU 6428 Problem C. Calculate 莫反+积性函数+线性筛

HDU 6428 Problem C. Calculate 莫反+积性函数+线性筛

• • 题意
  • 思路
  • Code(2480MS)

题意

求 解 ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C ϕ ( g c d ( i , j 2 , k 3 ) ) m o d 2 30 求解\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\phi (gcd(i,j^2,k^3))\;\;mod\;\;2^{30} 求解i=1∑A​j=1∑B​k=1∑C​ϕ(gcd(i,j2,k3))mod230

思路

首 先 要 把 ϕ 和 g c d 分 开 ， 即 ϕ ( n ) = ∑ d ∣ n ( ϕ ∗ μ ) ( d ) ， 证 明 如 下 ： 首先要把\phi和gcd分开，即\phi(n)=\sum_{d|n}(\phi*\mu)(d)，证明如下： 首先要把ϕ和gcd分开，即ϕ(n)=∑d∣n​(ϕ∗μ)(d)，证明如下：
ϕ ( n ) = ( μ ∗ i d ) ( n ) \phi(n)=(\mu*id)(n) ϕ(n)=(μ∗id)(n)

∑ d ∣ n μ ( d ) n d \sum_{d|n}\mu(d)\frac{n}{d} d∣n∑​μ(d)dn​

∑ d ∣ n μ ( d ) ∑ d ′ ∣ n d ϕ ( d ′ ) \sum_{d|n}\mu(d)\sum_{d'|\frac{n}{d}}\phi(d') d∣n∑​μ(d)d′∣dn​∑​ϕ(d′)

∑ d d ′ ∣ n μ ( d ) ϕ ( d ′ ) \sum_{dd'|n}\mu(d)\phi(d') dd′∣n∑​μ(d)ϕ(d′)

∑ d ∣ n ∑ d ′ ∣ d μ ( d ′ ) ϕ ( d d ′ ) \sum_{d|n}\sum_{d'|d}\mu(d')\phi(\frac{d}{d'}) d∣n∑​d′∣d∑​μ(d′)ϕ(d′d​)

∑ d ∣ n ( ϕ ∗ μ ) ( d ) \sum_{d|n}(\phi*\mu)(d) d∣n∑​(ϕ∗μ)(d)

所 以 原 式 变 为 ： 所以原式变为： 所以原式变为：

∑ i = 1 A ∑ j = 1 B ∑ k = 1 C ∑ d ∣ i d ∣ j 2 d ∣ k 3 ( ϕ ∗ μ ) ( d ) \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{d|i\;d|j^2\;d|k^3}(\phi*\mu)(d) i=1∑A​j=1∑B​k=1∑C​d∣id∣j2d∣k3∑​(ϕ∗μ)(d)

∑ d = 1 A ( ϕ ∗ μ ) ( d ) ∑ i = 1 d ∣ i A ∑ j = 1 d ∣ j 2 B ∑ k = 1 d ∣ k 3 C 1 \sum_{d=1}^{A}(\phi*\mu)(d)\sum_{i=1\;d|i}^A\sum_{j=1\;d|j^2}^B\sum_{k=1\;d|k^3}^C1 d=1∑A​(ϕ∗μ)(d)i=1d∣i∑A​j=1d∣j2∑B​k=1d∣k3∑C​1
\left \lceil \right \rceil
观 察 后 面 式 子 ， 对 于 一 个 x k ， 若 d ∣ x k ， 先 把 d 分 解 为 ∏ p i a i . 观察后面式子，对于一个x^k，若d|x^k，先把d分解为\prod p_i^{a_i}. 观察后面式子，对于一个xk，若d∣xk，先把d分解为∏piai​​.
则 ∏ p i a i ∣ x k ， 得 ∏ p i ⌈ a i k ⌉ ∣ x ， 所 以 设 则\prod p_i^{a_i}|x^k，得\prod p_i^{\left \lceil \frac{a_i}{k} \right \rceil }|x，所以设 则∏piai​​∣xk，得∏pi⌈kai​​⌉​∣x，所以设

f k ( n ) = ∏ p i ⌈ a i k ⌉ f_k(n)=\prod p_i^{\left \lceil \frac{a_i}{k} \right \rceil } fk​(n)=∏pi⌈kai​​⌉​

则 ： 则： 则：

a n s = ∑ d = 1 A ( ϕ ∗ μ ) ( d ) A f 1 ( d ) B f 2 ( d ) C f 3 ( d ) ans=\sum_{d=1}^{A}(\phi * \mu)(d)\frac{A}{f_1(d)}\frac{B}{f_2(d)}\frac{C}{f_3(d)} ans=d=1∑A​(ϕ∗μ)(d)f1​(d)A​f2​(d)B​f3​(d)C​

对 于 f k ( n ) ， 类 似 分 解 n 的 形 式 。 对于f_k(n)，类似分解n的形式。 对于fk​(n)，类似分解n的形式。
分 解 质 因 子 的 过 程 中 ， 记 录 质 因 子 的 指 数 ， 每 次 质 因 子 + 1 时 ， 若 % k = 1 时 ， 说 明 该 向 上 取 整 了 ， 于 是 f k ( n ) ∗ = 该 质 因 子 . 分解质因子的过程中，记录质因子的指数，每次质因子+1时，若\%k=1时，说明该向上取整了，于是f_k(n)*=该质因子. 分解质因子的过程中，记录质因子的指数，每次质因子+1时，若%k=1时，说明该向上取整了，于是fk​(n)∗=该质因子.

由 于 ϕ 和 μ 都 是 积 性 函 数 ， 卷 积 之 后 还 是 积 性 函 数 ， 设 g ( d ) = ( ϕ ∗ μ ) ( d ) ， 则 由于\phi和\mu都是积性函数，卷积之后还是积性函数，设g(d)=(\phi*\mu)(d)，则 由于ϕ和μ都是积性函数，卷积之后还是积性函数，设g(d)=(ϕ∗μ)(d)，则

ϕ ( n ) = ∑ d ∣ n g ( d ) \phi(n)=\sum_{d|n}g(d) ϕ(n)=d∣n∑​g(d)

那 么 可 以 得 ： 那么可以得： 那么可以得：

ϕ ( p k ) = ϕ ( p k − 1 ) + g ( p k ) \phi(p^k)=\phi(p^{k-1})+g(p^k) ϕ(pk)=ϕ(pk−1)+g(pk)

g ( p k ) = ϕ ( p k ) − ϕ ( p k − 1 ) g(p^k)=\phi(p^k)-\phi(p^{k-1}) g(pk)=ϕ(pk)−ϕ(pk−1)

g ( p k ) = ( p − 1 ) p k − 1 − ( p − 1 ) p k − 2 g(p^k)=(p-1)p^{k-1}-(p-1)p^{k-2} g(pk)=(p−1)pk−1−(p−1)pk−2

g ( p k ) = ( p − 1 ) 2 p k − 2 g(p^k)=(p-1)^2p^{k-2} g(pk)=(p−1)2pk−2

当 我 们 欧 拉 筛 的 过 程 中 ： 当我们欧拉筛的过程中： 当我们欧拉筛的过程中：

g ( 1 ) = 1 g(1)=1 g(1)=1

g ( p ) = p − 2 g(p)=p-2 g(p)=p−2

g ( p k ) = ( p − 1 ) 2 p k − 2 g(p^{k})=(p-1)^2p^{k-2} g(pk)=(p−1)2pk−2

g ( p 1 k 1 p 2 k 2 ) = g ( p 1 k 1 ) g ( p 2 k 2 ) g(p_1^{k_1}p_2^{k_2})=g(p_1^{k_1})g(p_2^{k_2}) g(p1k1​​p2k2​​)=g(p1k1​​)g(p2k2​​)

. . . . . . ...... ......

Code(2480MS)

#include "bits/stdc++.h"
using namespace std;typedef long long ll;const ll mod = (1ll << 30);const int N = 1e7 + 10;
bool is_prime[N];
int prime[N], cnt;
int g[N];
int f1[N], f2[N], f3[N];
int deg[N];void init() {f1[1] = f2[1] = f3[1] = g[1] = 1;for(int i = 2;i < N; i++) {f1[i] = i;if(!is_prime[i]) prime[++cnt] = f2[i] = f3[i] = i, g[i] = i - 2, deg[i] = 1;for(int j = 1;j <= cnt && i * prime[j] < N; j++) {int now = i * prime[j];is_prime[now] = 1;if(i % prime[j] == 0) {deg[now] = deg[i] + 1;int num = 1, tmp = i;while(num <= 3 && tmp % prime[j] == 0) num++, tmp /= prime[j];if(num == 1) g[now] = g[i] * g[prime[j]];else if(num == 2) g[now] = g[i / prime[j]] * (prime[j] - 1) * (prime[j] - 1);else g[now] = g[i] * prime[j];f2[now] = f2[i] * (deg[now] % 2 == 1 ? prime[j] : 1);f3[now] = f3[i] * (deg[now] % 3 == 1 ? prime[j] : 1);break;}else {deg[now] = 1;f2[now] = f2[i] * f2[prime[j]];f3[now] = f3[i] * f3[prime[j]];g[now] = g[i] * g[prime[j]];}}}
}void solve() {init();int _; scanf("%d",&_);while(_--) {int A, B, C; scanf("%d%d%d",&A,&B,&C);ll ans = 0;for(int d = 1;d <= A; d++) {ans = (ans + 1ll * g[d] * (A / f1[d]) % mod * (B / f2[d]) % mod * (C / f3[d]) % mod) % mod;}printf("%lld\n",(ans % mod + mod) % mod);}
}signed main() {solve();
}