【洛谷P2158】仪仗队【欧拉函数】

l i n k link link

方阵是关于对角线对称的 所以只用求出半个方阵能看见的人 再 × 2 times 2 ×2即可
还有 3 3 3个特殊点 即对角线和两边 有 3 3 3个

能被看见的人 ( i , j ) (i,j) (i,j) 需满足 g c d ( i , j ) = 1 gcd(i,j)=1 gcd(i,j)=1 因为他一定可以把所有 ( k x , k y ) (kx,ky) (kx,ky)挡住
然后欧拉函数

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=4e4+5;
int phi[N],n,ans;
void Prime(int n)
{
	for(int i=1;i<=n;i++)
		phi[i]=i;
	for(int i=2;i<=n;i++)
		if(phi[i]==i)
			for(int j=i;j<=n;j+=i)
				phi[j]=phi[j]/i*(i-1);
	
} 
int main()
{
	scanf("%d",&n);
	Prime(n);
	for(int i=2;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702540.html