SPOJ Problem Set (classical)

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, 0<=a,b,c<=N ;

莫比乌斯反演，十分的巧妙。

GCD(a,b)的题十分经典。这题扩展到GCD(a,b,c)加了一维，但是思想却是相同的。

设f(d) = GCD(a,b,c) = d的种类数；

F(n) 为GCD(a,b,c) = d 的倍数的种类数, n%a == 0 n%b==0 n%c==0。

即：F(d) = (N/d)*(N/d)*(N/d);

则f(d) = sigma( mu[n/d]*F(n), d|n )

由于d = 1 所以f(1) = sigma( mu[n]*F(n) ) = sigma( mu[n]*(N/n)*(N/n)*(N/n) );

由于0能够取到，所以对于a,b,c 要讨论一个为0 ，两个为0的情况 (3种).

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 typedef long long LL;

 const int maxn = +;

 bool s[maxn];

 int prime[maxn],len = ;

 int mu[maxn];

 void  init()

 {

     memset(s,true,sizeof(s));

     mu[] = ;

     for(int i=;i<maxn;i++)

     {

         if(s[i] == true)

         {

             prime[++len]  = i;

             mu[i] = -;

         }

         for(int j=;j<=len && (long long)prime[j]*i<maxn;j++)

         {

             s[i*prime[j]] = false;

             if(i%prime[j]!=)

                 mu[i*prime[j]] = -mu[i];

             else

             {

                 mu[i*prime[j]] = ;

                 break;

             }

         }

     }

 }

 int main()

 {

     int n,T;

     init();

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         LL sum = ;

         for(int i=;i<=n;i++)

             sum = sum + (long long)mu[i]*(n/i)*(n/i)*;

         for(int i=;i<=n;i++)

             sum = sum + (long long)mu[i]*(n/i)*(n/i)*(n/i);

         printf("%lld\n",sum);

     }

     return ;

 }

巴特西

spoj 7001. Visible Lattice Points GCD问题莫比乌斯反演

SPOJ Problem Set (classical)

7001. Visible Lattice Points

Problem code: VLATTICE

最新文章

热门文章

巴特西

spoj 7001. Visible Lattice Points GCD问题 莫比乌斯反演

SPOJ Problem Set (classical)

7001. Visible Lattice Points

Problem code: VLATTICE

最新文章

热门文章

spoj 7001. Visible Lattice Points GCD问题莫比乌斯反演