题解 P2158 【[SDOI2008]仪仗队】
萌新钟爱数论！
先说点题外话
欧拉函数： φ(n)即1到n中与与n互质的数的个数
欧拉函数的线性筛法 该算法可以在线性时间内筛素数的同时求出所有数的欧拉函数,需要用到以下3 性质(其中的p为质数)
性质1.φ(p)=p-1 因为质数p除了1以外的因数只有p,故1至p的整数只有p与p不互质
性质2.如果i mod p=0,那么φ(ip)=p*φ(i)
性质3.若i mod p!=0,那么φ(ip)=(p-1)*φ(i)
再结合一下素数的欧拉筛就可以都求出来了 什么？你不知道欧拉筛素数？
回到题目上来
首先,题目主要是求从(1,1)能看到的点的个数 先考虑只有(2，2)的时候,3个点,根据图明显看出,只需要计算下三角,结果=下三 的个数乘2再加1(斜率为1的点)。 那么我们只需要计算斜率从0到1之间的个数就行了,不包括1,包括0。结果设为 sum,那么最终就是2sum+1。
(2,2)只有一个斜率为0的。
(3,3)斜率有0,1/2(0已经算过了,以后不再算了),其实就多了一个斜率为1/2的。
(4,4)的时候,有1/3,2/3两个,比以前多了2个。
(5,5)的时候,有1/4,2/4(1/2已经有过了),3/4,所以也是2个。
(6,6)的时候,有1/5,2/5,3/5,4/5,之前都没有,所以多了4个
(7,7)得到时候,有1/6,2/6(1/3已经有了),3/6(1/2已经有了),4/6(2/3已经有 了),5/6,所以只剩2个。
从上面可以发现一个规律,对于n*n,可以从1,1连接到(n,1)到(n,n)上,斜率将 会是1/n,,2/n …(n-1)/n。 凡是分子和分母能够约分的也就是有公约数,前面都已经有过了。所以每次添 的个数就是分子和分母互质的个数。 那么问题就转换为,对于一个数n,求小于n的于n互质的数的个数,这不就是欧拉 函数么!
那这道题几乎就成了一道模板题了
AC code
#include<bits/stdc++.h>
using namespace std;
int n,ans,tot;
int zhi[40010],fai[40010];//注意分析好每个数组代表什么，fai为欧拉函数值，zhi为质数值
bool pri[40010];//pri应该很熟悉吧，欧拉筛质数的判断是否是质数的数组
void shai()
{ fai[1]=1;
for(int i=2;i<=n;i++)
{ if(!pri[i])
{ zhi[++tot]=i;
fai[i]=i-1;//性质1
}
for(int j=1;j<=tot&&i*zhi[j]<=n;j++)
{ pri[i*zhi[j]]=1;
if(i%zhi[j]==0)//性质2
{ fai[i*zhi[j]]=fai[i]*zhi[j];
break;
}
else //性质3
fai[i*zhi[j]]=fai[i]*(zhi[j]-1);
}
}
}
int main()
{ scanf("%d",&n);
shai();
for(int i=1;i<=n;i++)
ans+=fai[i];//累加就是可看到的人数
printf("%d",2*ans+1);//别忘了还有上半个三角形和斜率为1的那一个
return 0;
}//真心感觉自己写的这篇题解，很用心，超过别的了吧
希望给个赞，qwq