【BZOJ2190】仪仗队（数论）

题面

题解

对于题意，可以考虑

如果有\((i,j)\)能够被看见

那么，\((ki,kj)\)就一定不能看见

所以，如果一个点能够被看见，则有\(gcd(i,j)=1\)

先强制\(i>j\)

所以，对于每一个\(i\)，能够有的贡献是\(φ(i)\)

所以，直接求和即可，还有\(3\)个点直接暴力加上即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

int N;

int phi(int x)

{

	int ans=x;

	for(int i=2,l=sqrt(x);i<=l;++i)

		if(x%i==0)

		{

			ans=1ll*ans*(i-1)/i;

			while(x%i==0)x/=i;

		}

	if(x>1)ans=1ll*ans*(x-1)/x;

	return ans;

}

int main()

{

	cin>>N;

	int tot=0;

	for(int i=2;i<N;++i)

		tot+=phi(i);

	cout<<2*tot+3<<endl;

	return 0;

}

巴特西

【BZOJ2190】仪仗队（数论）

【BZOJ2190】仪仗队（数论）

题面

题解

最新文章

热门文章