莫比乌斯反演

Visible Trees

 1 /*************************************************************************
 2     > File Name: bb.cpp
 3     > Author: yijiull
 4     > Mail: 1147161372@qq.com 
 5     > Created Time: 2017年10月02日 星期一 19时21分27秒
 6  ************************************************************************/
 7 
 8 #include <iostream>
 9 #include <cstring>
10 #include <cstdio>
11 using namespace std;
12 const int maxn = 1e5+10;
13 #define ll long long 
14 int pri[maxn], mu[maxn];
15 
16 void init(){
17     int cnt = 0;
18     mu[1] = 1;
19     for(int i = 2; i < maxn; i++) {
20         if(!pri[i]) {
21             pri[cnt++] = i;
22             mu[i] = -1;
23         }
24         for(int j = 0; j < cnt; j++) {
25             if(pri[j] * i > maxn) break;
26             int t = pri[j] * i;
27             pri[t] = 1;
28             if(i % pri[j] == 0) {
29                 mu[t] = 0;
30                 break;
31             } else {
32                 mu[t] = -mu[i];
33             }
34         }
35     }
36 }
37 
38 int main(){
39     int t;
40     init();
41     scanf("%d", &t);
42     while(t--) {
43         int n, m;
44         scanf("%d %d", &n, &m);
45         ll ans = 0;
46         if(n < m) swap(n, m);
47         for(int i = 1; i <= m; i++) ans += 1LL * mu[i] * (n/i) * (m/i);
48         printf("%lld
", ans);
49     }
50 }

View Code

Visible Lattice Points

SPOJ - VLATTICE

 1 /*************************************************************************
 2     > File Name: bb.cpp
 3     > Author: yijiull
 4     > Mail: 1147161372@qq.com 
 5     > Created Time: 2017年10月02日 星期一 19时21分27秒
 6  ************************************************************************/
 7 
 8 #include <iostream>
 9 #include <cstring>
10 #include <cstdio>
11 using namespace std;
12 const int maxn = 1e6+10;
13 #define ll long long 
14 int pri[maxn], mu[maxn];
15 
16 void init(){
17     int cnt = 0;
18     mu[1] = 1;
19     for(int i = 2; i < maxn; i++) {
20         if(!pri[i]) {
21             pri[cnt++] = i;
22             mu[i] = -1;
23         }
24         for(int j = 0; j < cnt; j++) {
25             if(pri[j] * i > maxn) break;
26             int t = pri[j] * i;
27             pri[t] = 1;
28             if(i % pri[j] == 0) {
29                 mu[t] = 0;
30                 break;
31             } else {
32                 mu[t] = -mu[i];
33             }
34         }
35     }
36 }
37 
38 int main(){
39     int t;
40     init();
41     scanf("%d", &t);
42     while(t--) {
43         int n, m;
44         scanf("%d", &n);
45         ll ans = 3;
46         for(int i = 1; i <= n; i++) ans += 1LL * mu[i] * (n/i) * (n/i) * (n/i+3) ;
47         printf("%lld
", ans);
48     }
49 }
50 f

View Code

GCD

HDU - 1695

这里有另一种易懂的证明~ 链接

 1 /*************************************************************************
 2     > File Name: bb.cpp
 3     > Author: yijiull
 4     > Mail: 1147161372@qq.com 
 5     > Created Time: 2017年10月02日 星期一 19时21分27秒
 6  ************************************************************************/
 7 
 8 #include <iostream>
 9 #include <cstring>
10 #include <cstdio>
11 using namespace std;
12 const int maxn = 1e5+10;
13 #define ll long long 
14 int pri[maxn], mu[maxn];
15 
16 void init(){
17     int cnt = 0;
18     mu[1] = 1;
19     for(int i = 2; i < maxn; i++) {
20         if(!pri[i]) {
21             pri[cnt++] = i;
22             mu[i] = -1;
23         }
24         for(int j = 0; j < cnt; j++) {
25             if(pri[j] * i > maxn) break;
26             int t = pri[j] * i;
27             pri[t] = 1;
28             if(i % pri[j] == 0) {
29                 mu[t] = 0;
30                 break;
31             } else {
32                 mu[t] = -mu[i];
33             }
34         }
35     }
36 }
37 
38 int main(){
39     int t;
40     init();
41    // freopen("in.txt", "r", stdin);
42     int kase = 0;
43     scanf("%d", &t);
44     while(t--) {
45         int n, m, k;
46         scanf("%d %d %d %d %d", &n, &n, &m, &m, &k);
47         if(k == 0) {
48             printf("Case %d: 0
", ++kase);
49             continue;
50         }
51         ll ans1 = 0, ans2 = 0;
52         m /= k;
53         n /= k;
54         if(n > m) swap(n, m);
55         for(int i = 1; i <= n; i++) {
56             ans1 += 1LL * mu[i] * (n/i) * (m/i);
57             ans2 += 1LL * mu[i] * (n/i) * (n/i);
58         }
59         printf("Case %d: %lld
", ++kase, ans1 - ans2/2);
60     }
61 }

View Code