洛谷P2158 [SDOI2008]仪仗队

傷城~ 2022-05-25 01:28 143阅读 0赞

## 题目描述 ##

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \* N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 ![1149.png][] 现在，C君希望你告诉他队伍整齐时能看到的学生人数。

## 输入输出格式 ##

输入格式：

共一个数N

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

输出样例\#1： 复制

##     ##

## 说明 ##

【数据规模和约定】

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

参考：[https://blog.csdn.net/largecub233/article/details/60883194][https_blog.csdn.net_largecub233_article_details_60883194]

裸的欧拉函数题。e(i)为有多少个小于i的与i互质的数。

可以把点看做坐标轴。求左下角的点是(1,1)，然后求有多少个点(1,1)相连斜率不同的一次函数y=kx。求k的个数。

因为k=y/x。想要y/x不同，y与x一定互质(k=y/x=y\*z/x\*z)，不同的互质数相除又一定不同。所以只要求在n范围内有多少对x,y互质。

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define Maxn 40010
    int ans, n, e[Maxn];
    int main()
    {
    	cin >> n;
    	if (n == 1)
    	{
    		cout << 0;
    		return 0;
    	}
    	for (int i = 2; i < n; i++)
    	{
    		if (!e[i])//可以知道，当这时，i一定是质数，思路和上面差不多
    		{
    			for (int j = i; j <= n; j+=i)//查看质数i的倍数
    			{
    				if (!e[j]) e[j] = j;//如果phi[j]一开始是0，先假设1~j都和j互质
                //但要注意，这个赋值不可以一开始初始化
                //因为我们要靠这个数组来判断i是不是质数
    				e[j] = e[j] / i*(i - 1);//先把a割成每段都是i个的，再乘以（i-1）不就把i的倍数给漏掉了吗？
                //当然喽，这里phi[j]显然是i的倍数 因为j+=i
    			}
    		}
    		ans += e[i];
    	}
    	cout << ans * 2 + 3;
    	return 0;
    }

[1149.png]: /images/20220525/2d97eba63d574685ab2bed9cfe4f50e4.png
[https_blog.csdn.net_largecub233_article_details_60883194]: https://blog.csdn.net/largecub233/article/details/60883194