首页 > 代码库 > 【BZOJ】【2190】【SDOI2008】仪仗队
【BZOJ】【2190】【SDOI2008】仪仗队
欧拉函数/莫比乌斯函数
Orz iwtwiioi
这个嘛……很明显在同一条线上的两个点一定是满足 x1*k=x2,y1*k=y2，（好吧这个表示方式有点傻逼，懂得就好了）那么这条线上的点只有第一个会被看到，即x,y互质的那一个点（如果gcd(x,y)==k>1那么肯定在它前面还有点(x/k,y/k) ）
但是马上你就会指着鼻子骂我说这特么不是胡扯么……(2,1) 和 (4,2)明明都能被看到！那是因为这里的“坐标原点”是(1,1)啊……所以坐标都减个1就好了→_→
所以就是求 ………………看iwtwiioi的博客去吧- -b 我不会用LeTeX……
嗯就是求：（原谅我截图跑……iwtwiioi实在太神了）
这样一个东西……就是对于每个x，求一共有多少个y与它互质，这不就是欧拉函数的定义么→_→
所以可以写成
【然后再乘二（x和y交换算两组）】
最后还有一点细节要注意：(1,1)这个点统计了两次，(1,0) 和 (0,1)这两个点没有算。
还有一种姿势，如果是用莫比乌斯函数写的话，第一个和式还可以写成：【Orz lqybzx】
sigma{ mu[i]*(n/i)*(n/i) } （不要吐槽我的语法……）
我的代码：（线性筛模板参见《线性筛法与积性函数》——贾志鹏）
1 /************************************************************** 2 Problem: 2190 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:24 ms 7 Memory:1624 kb 8 ****************************************************************/ 9 10 //BZOJ 219011 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 using namespace std;20 int getint(){21 int v=0,sign=1; char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}24 return v*=sign;25 }26 /******************tamplate*********************/27 const int N=40010;28 int phi[N],prime[N];29 bool check[N];30 void getphi(int n){31 memset(check,0,sizeof check);32 phi[1]=1;33 int tot=0;34 F(i,2,n){35 if(!check[i]){36 prime[tot++]=i;37 phi[i]=i-1;38 }39 rep(j,n){40 if(i*prime[j]>n) break;41 check[i*prime[j]]=1;42 if(i % prime[j]==0){43 phi[i*prime[j]]=phi[i]*prime[j];44 break;45 }46 else phi[i*prime[j]]=phi[i]*(prime[j]-1);47 }48 }49 }50 int main(){51 int n=getint(),ans=0;52 getphi(n);53 F(i,1,n-1)54 ans+=phi[i];55 ans=ans*2+1;56 printf("%d\n",ans);57 return 0;58 }
1 /************************************************************** 2 Problem: 2190 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:28 ms 7 Memory:1624 kb 8 ****************************************************************/ 9 10 //BZOJ 219011 #include<cstdio>12 #include<cstring>13 #include<cstdlib>14 #include<iostream>15 #include<algorithm>16 #define rep(i,n) for(int i=0;i<n;++i)17 #define F(i,j,n) for(int i=j;i<=n;++i)18 #define D(i,j,n) for(int i=j;i>=n;--i)19 using namespace std;20 int getint(){21 int v=0,sign=1; char ch=getchar();22 while(!isdigit(ch)) {if(ch==‘-‘) sign=-1; ch=getchar();}23 while(isdigit(ch)) {v=v*10+ch-‘0‘; ch=getchar();}24 return v*sign;25 }26 /*******************template********************/27 const int N=40001;28 int prime[N],mu[N];29 bool check[N];30 void getmu(int n){31 memset(check,0,sizeof check);32 mu[1]=1;33 int tot=0;34 F(i,2,n){35 if(!check[i]){36 prime[tot++]=i;37 mu[i]=-1;38 }39 rep(j,tot){40 if(i*prime[j]>n) break;41 check[i*prime[j]]=true;42 if(i%prime[j]==0){43 mu[i*prime[j]]=0;44 break;45 }46 else mu[i*prime[j]]=-mu[i];47 }48 }49 }50 int main(){51 int n,ans=0;52 n=getint();53 n--;54 getmu(n);55 F(i,1,n) ans+=mu[i]*(n/i)*(n/i);56 ans=ans+2;57 printf("%d\n",ans);58 return 0;59 }60
【BZOJ】【2190】【SDOI2008】仪仗队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。