P2568 GCD

提交11.33k

通过4.55k

时间限制1.00s

内存限制250.00MB

提交答案加入题单复制题目

做题计划（首页）

个人题单

团队题单

保存

选择团队

保存

题目提供者洛谷

难度提高+/省选-

历史分数100

 提交记录  查看题解

 查看算法标签

进入讨论版

 查看讨论

 查看推荐

 复制Markdown  展开

给定正整数 nn，求 1le x,yle n1≤x,y≤n 且 gcd(x,y)gcd(x,y) 为素数的数对 (x,y)(x,y) 有多少对。

只有一行一个整数，代表nn。

一行一个整数表示答案。

输入 #1复制

4

输出 #1复制

4

样例输入输出 1 解释

对于样例，满足条件的 (x,y)(x,y) 为 (2,2)(2,2)，(2,4)(2,4)，(3,3)(3,3)，(4,2)(4,2)。

数据规模与约定

• 对于 100%100% 的数据，保证 1le nle10^71≤n≤107。

来源：bzoj2818。

本题数据为洛谷自造数据，使用 CYaRon 耗时 55 分钟完成数据制作。

#include
using namespace std;
#define int long long
const int N=1e7+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int n,phi[N],a[N],sum,ans;
void get_phi()
{
	for(int i=1;i<=n;i++)phi[i]=i;
	for(int i=2;i<=n;i++)
		if(phi[i]==i)
		{
			for(int j=1;j*i<=n;j++)phi[i*j]=phi[i*j]*(i-1)/i;
			a[++sum]=i;
		}
}
signed main()
{
	n=fread(),get_phi();
	for(int i=1;i<=sum;i++)
	{
		ans--;
		for(int j=1;j<=n/a[i];j++)ans+=2*phi[j];
	}
	fwrite(ans);
	return 0;
}