SPOJ 7001. Visible Lattice Points （莫比乌斯反演）

7001. Visible Lattice Points

Problem code: VLATTICE

Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.

Input :
The first line contains the number of test cases T. The next T lines contain an interger N

Output :
Output T lines, one corresponding to each test case.

Sample Input :
3
1
2
5

Sample Output :
7
19
175

Constraints :
T <= 50
1 <= N <= 1000000

这题就是求gcd(a,b,c) = 1 a,b,c <=N 的对数。

用莫比乌斯反演可以求解。

设g(n)为gcd(x,y,z)=n的个数，f(n)为n | g(i*n)的个数，那么有f(n)=sigma(n|d,g(d))，那么g(n)=sigma(n|d, mu(d/n)*f(d))，我们要求g(1)，则g(1)=sigma(n|d, mu(d)*f(d))，

因为f(d)=(n/d)*(n/d)*(n/d)，所以g(1)=sigma( mu(d)*(n/d)*(n/d)*(n/d) ).

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2013/8/21 18:28:50
 4 File Name     :F:2013ACM练习专题学习数学莫比乌斯反演SPOJ7001.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 const int MAXN = 1000000;
21 bool check[MAXN+10];
22 int prime[MAXN+10];
23 int mu[MAXN+10];
24 void Moblus()
25 {
26     memset(check,false,sizeof(check));
27     mu[1] = 1;
28     int tot = 0;
29     for(int i = 2; i <= MAXN; i++)
30     {
31         if( !check[i] )
32         {
33             prime[tot++] = i;
34             mu[i] = -1;
35         }
36         for(int j = 0; j < tot; j++)
37         {
38             if(i * prime[j] > MAXN) break;
39             check[i * prime[j]] = true;
40             if( i % prime[j] == 0)
41             {
42                 mu[i * prime[j]] = 0;
43                 break;
44             }
45             else
46             {
47                 mu[i * prime[j]] = -mu[i];
48             }
49         }
50     }
51 }
52 int main()
53 {
54     //freopen("in.txt","r",stdin);
55     //freopen("out.txt","w",stdout);
56     int T,n;
57     Moblus();
58     scanf("%d",&T);
59     while(T--)
60     {
61         scanf("%d",&n);
62         long long ans = 3;
63         for(int i = 1;i <= n;i++)
64             ans += (long long)mu[i]*(n/i)*(n/i)*((n/i)+3);
65         printf("%lld
",ans);
66     }
67     return 0;
68 }