【日常学习】【欧拉函数】codevs2296 仪仗队题解

绝地灬酷狼 2022-08-05 04:18 103阅读 0赞

题目来源：SDOI2008

文章被剽窃很严重啊 所以以后都带上版权信息

先上题目

题目描述 Description

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \* N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

现在，C君希望你告诉他队伍整齐时能看到的学生人数。

![2296.png][]

输入描述 Input Description

共一个数N。

输出描述 Output Description

共一个数，即C君应看到的学生人数。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于 30% 的数据，1<N<1000

对于 100% 的数据，1<N<40000

这道题目乍一看很拿下手，其实不难发现，每条线上看到第一个人就是说**每一个可能的斜率上只能看见一个人**。

这样问题变成了求可能存在的斜率数。斜率怎么表示呢？由于每个点都是以坐标形式表示，斜率就是y/x，如果x和y的最大公因数是1，即gcd（x,y）=1，那么它一定是这个斜率上的第一个点。因为如果他们的最大公因数不是1，比如是2，那么x和y可以约掉2，（4,2）就可以变成（2,1），因此（4,2）不是这条斜率上的第一个点。

那么有多少个gcd（x,y）=1的点呢？我们发现，整张图关于y=x对称，因此只需考虑下面一半即可。而斜率为0或n的情况很特殊，在对称轴上或边缘，先排除。其他的点，我们观察后可以发现，每一列上，横坐标x不变，**y<x**,而这一列上的出现新斜率的节点满足**y与x除了1以外没有其他公因数。即y与x互质。**每一列上与x互质的y有多少个呢？有欧拉函数phi(x)个。

欧拉函数：对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如φ(8)=4，因为1,3,5,7均和8互质。

因此，我们只需要求出这2到n-1的欧拉函数，乘以2再加上剩余的边缘和对称轴上的三个点，就可得出正确结果了。

这道题告诉我们：**遇到gcd=1的情况，应考虑欧拉函数**

上代码！

//codevs2296 SDOI08 仪仗队 欧拉函数
    //copyright by ametake 
    #include
       
        
    #include
        
         
    using namespace std;
    
    const int maxn=40000+10;
    int phi[maxn]={0};
    int i,n;
    
    void getphi()//Eratosthenes while eular phi一边筛法一边求欧拉函数 没有标记为合数的下一个书就是质数  
    {
    	phi[1]=1;//exception
    	for (int i = 2;i <= n;i++)
    	{
    		if (!phi[i])//if i is a prime number
    		{
    			for (int j = i;j <= n;j += i)//for every i's multiple
    			{
    				if (!phi[j]) phi[j] = j;//now j is composite number so not 0 
    				phi[j]=phi[j] / i * (i-1);
    			}
    		}
    	}
    }
    
    int main()
    {
    	scanf("%d",&n);
    	getphi();
    	int ans=0;
    	for (i = 2;i <= n-1;i++) ans += (phi[i] * 2); 
    	ans += 3;
    	printf("%d",ans);
    	return 0;
    }

这里参考了ghy1953的欧拉函数模板 简洁明了 埃拉托色尼筛法与欧拉函数结合一次搞定

——亦以明死生之大，匹夫之有重于社稷也。

[http_blog.csdn.net_ametake]: http://blog.csdn.net/ametake
[2296.png]: http://codevs.cn/media/image/problem/2296.png