TLE求调
查看原帖
TLE求调
1061904
huhaoranshuai楼主2024/7/27 15:27
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=1e6+9;
ll read()
{
	ll f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-48;
		ch=getchar();
	}
	return f*x;
}
ll n,a[N],sg[N];
bool flag[N];
ll SG(ll xd)
{
	ll k=0;
	if(sg[xd]!=-1) return sg[xd];
	for(ll i=1;i*i<=xd;i++)
	{
		if(xd%i==0)
		{
			if(xd>i)k^=SG(i);
			if(i!=sqrt(xd)&&xd>xd/i) k^=SG(xd/i);
		}
	}
	memset(flag,0,sizeof(flag));
	for(ll i=1;i*i<=xd;i++)
	{
		if(xd%i==0)
		{
			if(xd>i) flag[k^SG(i)]=true;
			if(i!=sqrt(xd)&&xd>xd/i) flag[k^SG(xd/i)]=true;
		}
	}
	ll pos=0;
	while(flag[pos]) pos++;
	return sg[xd]=pos;
}
int main()
{
	sg[0]=0;
	while(scanf("%d",&n)!=EOF)
	{
		memset(sg,-1,sizeof(sg));
		ll sum=0;
		for(ll i=1;i<=n;i++)
		{
			a[i]=read();
			a[i]=SG(a[i]);
		}
		for(ll i=1;i<=n;i++)
		{
			sum^=a[i];
		}
		if(sum==0)
		printf("rainbow\n");
		else
		printf("freda\n");
	}
	return 0;
}
2024/7/27 15:27
加载中...