HELP 为什么会RE
  • 板块学术版
  • 楼主king_xbz
  • 当前回复9
  • 已保存回复9
  • 发布时间2020/7/17 11:33
  • 上次更新2023/11/6 22:58:37
查看原帖
HELP 为什么会RE
244059
king_xbz楼主2020/7/17 11:33

这个筛一定范围内欧拉函数的程序为什么会RE?

题目是P1390 公约数的和

#include<bits/stdc++.h>
#define fint register int
#define h 5001
#define p 2094895
#define int long long
using namespace std;
int s[p],f[p];
int phi[p];
bool vis[p];
int prim[p];
inline int read();
inline int oula(int x);
signed main()
{
	int n;
	n=read();
	oula(n);
	for(fint i=1;i<=n;i++)
	for(fint j=i+i;j<=n;j+=i)
	f[j]+=i*phi[j/i];
	s[2]=f[2];
	for(fint i=3;i<=n;i++)
	s[i]=s[i-1]+f[i];
	cout<<s[n];
	return 0;
}
inline int oula(int x)
{
	int cnt=0;
	vis[1]=1;
	for(fint i=2;i<=x;i++)
	if(!vis[i])
	for(fint j=i*i;j<=x;j+=i)
	vis[j]=1;
	phi[1]=1;
	for(fint i=1;i<=x;i++)
	{
		if(!vis[i])
		prim[++cnt]=i,phi[i]=i-1;
		for(fint j=1;j<=cnt&&prim[j]*i<=x;j++) 
		if(i%prim[j]==0)
		{
			phi[i*prim[j]]=phi[i]*prim[j];
			break;
		}
		else
		phi[i*prim[j]]=phi[i]*phi[prim[j]];
	}
} 

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
2020/7/17 11:33
加载中...