A - Visible Lattice Points SPOJ - VLATTICE 容斥原理/莫比乌斯反演

缺乏、安全感 2021-09-30 01:22 231阅读 0赞

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long LL;
     4 const int N=1e6+10;
     5 const int INF=0x3f3f3f3f;
     6 int cas=1,T;
     7 int c[N];
     8 void init()
     9 {
    10     memset(c,0,sizeof(c));
    11     c[1]=1;
    12     for(int i=1;i<N;i++)
    13     {
    14         if(c[i]) for(int j=i<<1;j<N;j+=i) c[j]-=c[i];
    15         c[i]+=c[i-1];
    16     }
    17 }
    18 int p[N],vis[N],pn;
    19 void getMu(int *mu)  //O(n)
    20 {  
    21     memset(vis,0,sizeof(vis));  
    22     mu[1]=1;  
    23     pn=0;  
    24     for(int i=2; i<N; i++)  
    25     {  
    26         if(!vis[i]) { p[pn++]=i;mu[i]=-1; }  
    27         for(int j=0; j<pn&&i*p[j]<N; j++)  
    28         {  
    29             vis[i*p[j]]=1;  
    30             if(i%p[j]) mu[i*p[j]]=-mu[i];  
    31             else { mu[i*p[j]]=0;break;}  
    32         }  
    33         mu[i]+=mu[i-1];
    34     }  
    35 }  
    36 int main()
    37 {
    38     //freopen("1.in","w",stdout);
    39     //freopen("1.in","r",stdin);
    40     //freopen("1.out","w",stdout);
    41     //init();
    42     getMu(c);
    43     scanf("%d",&T);
    44     while(T--)
    45     {
    46         int n;
    47         scanf("%d",&n);
    48         LL ans=0;
    49         //for(int i=1;i<=n;i++) if(c[i]) ans+=c[i] * ((LL) (n/i+1)*(n/i+1)*(n/i+1)-1);
    50         for(int i=1;i<=n;)
    51         {
    52             int x=n/i;
    53             int y=n/x;
    54             ans+=(c[y]-c[i-1]) * ((LL) (n/i+1)*(n/i+1)*(n/i+1)-1);
    55             i=y+1;
    56         }
    57         printf("%lld\n",ans);
    58     }
    59     //printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);
    60     return 0;
    61 }

AC 0ms

转载于:https://www.cnblogs.com/cdyboke/p/6828137.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/8d237a31d07a45baa6cef4249af606c2.png