RE疑问
  • 板块P2568 GCD
  • 楼主oiyang
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/14 16:35
  • 上次更新2023/11/3 09:52:21
查看原帖
RE疑问
856309
oiyang楼主2023/7/14 16:35

为啥我把prime[j]>n/vis[i] 改成现在这样就好了?

void oula(int n)
{
	p[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0)
			vis[i]=i,prime[++cnt]=i,p[i]=i-1;
		for(int j=1;j<=cnt;j++)
		{
			if(prime[j]>vis[i] || prime[j]>n/i)
				break;
			vis[prime[j]*i]=prime[j];
			p[i*prime[j]]=p[i]*(i%prime[j] ?prime[j]-1 :prime[j]);
		}
	}
}
2023/7/14 16:35
加载中...