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 :

Sample Output :

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 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           
            14 #include 
            15 #include 
             
              16 #include 
              
               17 #include 
               
                18 #include 
                
                 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 else46 {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\n",ans);66 }67 return 0;68 }

转载地址：http://ceojo.baihongyu.com/

你可能感兴趣的文章