首页 > 代码库 > [SPOJ VLATTICE]Visible Lattice Points 数论 莫比乌斯反演
[SPOJ VLATTICE]Visible Lattice Points 数论 莫比乌斯反演
7001. Visible Lattice PointsProblem 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
题目大意
给定n*n*n的立方体,每个整数点除(0,0,0)之外都有一盏灯(抽象理解),问能看到多少盏灯(被盖住的灯不算)
解题思路
莫比乌斯反演/容斥原理的典型应用
用容斥原理来解释就是三个点都能被k整除的个数乘上莫比乌斯系数,求和即可
而三个点都能被k整除的个数就是floor(n/i)^3
注意到最大数据量为1000000 直接线性处理的办法可能TLE
而(n/i)在后面i>(n/2)的部分结果都为1 可以省去一次次计算,直接按mu的前缀和来处理
则我们就统计相同(n/i)的值是否出现两次,如果出现两次那么我们就开始按照前缀和的方法来处理
不优化 6200ms
优化后 490ms
code
优化前
#include <cstdio> #include <iostream> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #define sqr(x) ((x)*(x)) #define LL long long #define INF 0x3f3f3f3f #define PI acos(-1.0) #define eps 1e-10 #define mod 100000007ll using namespace std; LL n; LL com[1000005],pri[1000005],phi[1000005],pn,sum[1000005],mu[1000005]; LL a[1000005]; int main() { memset(com ,0 ,sizeof com); mu[1]=1; for (int i=2;i<=1000000ll;i++) { if (com[i]==0) { phi[i]=i-1; pri[++pn]=i; mu[i]=-1; // printf("%d\n", pri[pn]); // system("pause"); } for (int j=1;j<=pn&&pri[j]*i<=1000000ll;j++) { if (i%pri[j]) { phi[i*pri[j]]=phi[i]*(pri[j]-1); com[i*pri[j]]=1; mu[i*pri[j]]=-mu[i]; } else { phi[i*pri[j]]=phi[i]*(pri[j]); com[i*pri[j]]=1; mu[i*pri[j]]==0; break; } } } sum[0]=0; for (int i=1;i<=1000000ll;i++) sum[i]=sum[i-1]+phi[i]; int T; scanf("%d",&T); while (T--) { // n=1000000; LL ans=0; scanf("%lld",&n); for (int i=n;i;i--) { a[i]=(n/i)*(n/i)*(n/i); ans+=a[i]*mu[i]; } printf("%lld\n",ans+(sum[n]*2+1)*3+3); } return 0; }
优化后
#include <cstdio> #include <iostream> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #define sqr(x) ((x)*(x)) #define LL long long #define INF 0x3f3f3f3f #define PI acos(-1.0) #define eps 1e-10 using namespace std; int mu[1000005]; int com[1000005]; int pri[1000005],pn=0; int phi[1000005]; LL presum[1000005]; int musum[1000005]; int main() { memset(com,0,sizeof com); presum[1]=0; mu[1]=1; phi[1]=0; for (int i=2;i<=1000000;i++) { if (com[i]==0) { pri[++pn]=i; mu[i]=-1; phi[i]=i-1; } for (int j=1;j<=pn&&pri[j]*i<=1000000;j++) { if (i%pri[j]) { mu[i*pri[j]]=-mu[i]; com[i*pri[j]]=1; phi[i*pri[j]]=phi[i]*(pri[j]-1); } else { phi[i*pri[j]]=phi[i]*(pri[j]); mu[i*pri[j]]=0; com[i*pri[j]]=1; break; } } presum[i]=presum[i-1]+phi[i]; musum[i]=musum[i-1]+mu[i]; } int T; scanf("%d",&T); int a,b,c,d,k; while (T--) { int n; LL ans=0; scanf("%d",&n); int i; for (i=1;i<=n;i++) if ((n/i)==(n/(i+1))) break; else ans+=(LL)(n/i)*(n/i)*(n/i)*mu[i]; for (int j=(n/i);j;j--) ans+=(LL)(j)*(j)*(j)*(musum[n/(j)]-musum[n/(j+1)]); ans+=(LL)presum[n]*6+6; printf("%lld\n",ans); } return 0; }
[SPOJ VLATTICE]Visible Lattice Points 数论 莫比乌斯反演