SPOJ VLATTICE

VLATTICE - Visible Lattice Points

分析

　　求(i,j,k)=1的个数，i<=n,j<=n,k<=n。

　　和两个数的推法一样，直接推就好了。

　　最后计算时，坐标轴上有三个点计算不到，还有三个平面也没有计算到，加上。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 const int N = 1000100;
 6 LL mu[N],pri[N],tot;
 7 bool nopri[N];
 8 
 9 void getmu(int n) {
10     mu[1] = 1;
11     for (int i=2; i<=n; ++i) {
12         if (!nopri[i]) pri[++tot] = i,mu[i] = -1;
13         for (int j=1; j<=tot&&i*pri[j]<=n; ++j) {
14             nopri[i * pri[j]] = true;
15             if (i % pri[j] == 0) {
16                 mu[i * pri[j]] = 0;
17                 break;
18             }
19             mu[i * pri[j]] = -mu[i];
20         }
21     }
22     for (int i=1; i<=n; ++i) mu[i] += mu[i-1];
23 }
24 
25 LL calc1(int n) {
26     LL ans = 0;
27     int pos = 0;
28     for (int i=1; i<=n; i=pos+1) {
29         pos = n/(n/i);
30         ans += 1ll * (n/i) * (n/i) * (mu[pos] - mu[i-1]);
31     }
32     return ans;
33 }
34 LL calc2(int n) {
35     LL ans = 0;
36     int pos = 0;
37     for (int i=1; i<=n; i=pos+1) {
38         pos = n/(n/i);
39         ans += 1ll * (n/i) * (n/i) * (n/i) * (mu[pos] - mu[i-1]);
40     }
41     return ans;
42 }
43 int main() {
44     
45     getmu(1000000);
46     int T,n;
47     scanf("%d",&T);
48     while (T--) {
49         scanf("%d",&n);
50         printf("%lld
",calc1(n)*3+calc2(n)+3);
51     }
52     return 0;
53 }