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

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6428

题意

$$求解\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\phi (gcd(i,j^2,k^3))\;\;mod\;\;2^{30}$$

思路

$首先要把\phi和gcd分开，即\phi(n)=\sum_{dn}(\phi*\mu)(d)，证明如下：$ $$\phi(n)=(\mu*id)(n)$$

$$\sum_{dn}\mu(d)\frac{n}{d}$$

$$\sum_{dn}\mu(d)\sum_{d’\frac{n}{d}}\phi(d’)$$

$$\sum_{dd’n}\mu(d)\phi(d’)$$

$$\sum_{dn}\sum_{d’d}\mu(d’)\phi(\frac{d}{d’})$$

$$\sum_{dn}(\phi*\mu)(d)$$

$所以原式变为：$

$$\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{di\;dj^2\;dk^3}(\phi*\mu)(d)$$

$$\sum_{d=1}^{A}(\phi*\mu)(d)\sum_{i=1\;di}^A\sum_{j=1\;dj^2}^B\sum_{k=1\;dk^3}^C1$$

$观察后面式子，对于一个x^k，若dx^k，先把d分解为\prod p_i^{a_i}.$ $则\prod p_i^{a_i}x^k，得\prod p_i^{\left \lceil \frac{a_i}{k} \right \rceil }x，所以设$

$$f_k(n)=\prod p_i^{\left \lceil \frac{a_i}{k} \right \rceil }$$

$则：$

$$ans=\sum_{d=1}^{A}(\phi * \mu)(d)\frac{A}{f_1(d)}\frac{B}{f_2(d)}\frac{C}{f_3(d)}$$

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

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

$$\phi(n)=\sum_{dn}g(d)$$

$那么可以得：$

$$\phi(p^k)=\phi(p^{k-1})+g(p^k)$$

$$g(p^k)=\phi(p^k)-\phi(p^{k-1})$$

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

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

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

$$g(1)=1$$

$$g(p)=p-2$$

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

$$g(p_1^{k_1}p_2^{k_2})=g(p_1^{k_1})g(p_2^{k_2})$$

$$……$$

Code(2480MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
##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();
}