首页 > 代码库 > SPOJ 7001
SPOJ 7001
这次求的是三维的。如上篇一样，使用那个特殊的莫比乌斯反演来做。
需要注意的是，求得的只是从(1,1,1)到(n,n,n)的互质的个数，还要注意墙壁三面如(0,1,1)~(0,n,n)等。最后+3。因为是(0,0,1);
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 1000005using namespace std;typedef long long LL;int mobi[N];bool vis[N];int n;void initial(){ int i,j; for(i=1;i<N;i++) mobi[i]=1,vis[i]=false; for(i=2;i<N;i++) { if(vis[i]) continue; for(j=i;j<N;j+=i){ vis[j]=true; if((j/i)%i==0){ mobi[j]=0; continue; } mobi[j]=-mobi[j]; } }}int main(){ initial(); int T; scanf("%d",&T); while(T--){ scanf("%d",&n); LL ans=0; for(int i=1;i<=n;i++){ ans+=((LL)mobi[i]*(LL)(n/i)*(LL)(n/i)*(LL)(n/i)+3*(LL)mobi[i]*(LL)(n/i)*(LL)(n/i)); } ans+=3; printf("%lld\n",ans); } return 0;}
SPOJ 7001
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。