CH3B16 魔法珠

时间：2022-01-21 05:23:21

题意

3B16 魔法珠 0x3B「数学知识」练习

描述

Freda和rainbow是超自然之界学校(Preternatural Kingdom University，简称PKU)魔法学院的学生。为了展示新学的魔法，Ta们决定进行一场对弈~~~

起初Freda面前有n堆魔法珠，其中第i堆有ai颗。Freda和rainbow可以轮流进行以下操作：

1.选择n堆中魔法珠数量大于1的任意一堆。记该堆魔法珠的数量为p，p有b1、b2……bm这m个小于p的约数。

2.施展魔法把这一堆魔法珠变成m堆，每堆各有b1、b2……bm颗魔法珠。

3.选择这m堆中的一堆魔法珠，施展魔法令其消失。

注意一次操作过后，魔法珠的堆数会增加m-2，各堆中魔法珠数量的总和可能会发生变化。

当轮到某人操作时，如果每堆中魔法珠的数量均为1，那么ta就输了。

Freda和rainbow都采取最好的策略，从Freda开始。请你预测一下，谁能获胜呢？

输入格式

本题仅有一个测试点，包含多组数据，以EOF结尾。

每组数据的第一行包含一个整数n。

第二行包含n个整数ai。

输出格式

对于每组数据，在两人均采取最佳策略的前提下，若Freda能获胜，输出freda；若Rainbow能获胜，输出rainbow。

样例输入

3

2 2 2

3

1 3 5

样例输出

freda

rainbow

数据范围与约定

  • 1<=n<=100,1<=ai<=1000
        </article>

分析

这是一个公平组合游戏ICG，所以直接上SG函数即可。

总结一下，选一个走是mex，都要走是xor。

时间复杂度\(O(n^2)\)

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

co int N=1001;

int n,sg[N];

int fj(int x,int*a){

	int tot=a[1]=1;

	for(int i=2;i*i<=x;++i)if(x%i==0){

		a[++tot]=i;

		if(i*i!=x) a[++tot]=x/i;

	}

	return tot;

}

int SG(int x){

	if(sg[x]!=-1) return sg[x];

	int a[N];

	int tot=fj(x,a);

	bool v[N];

	memset(v,0,sizeof v);

	for(int i=1,k;i<=tot;++i){

		k=0;

		for(int j=1;j<=tot;++j)

			if(i!=j) k^=SG(a[j]);

		v[k]=1;

	}

	int t=0;

	while(v[t]) ++t;

	return sg[x]=t;

}

int main(){

//	freopen(".in","r",stdin),freopen(".out","w",stdout);

	memset(sg,-1,sizeof sg);

	sg[1]=0;

	while(~scanf("%d",&n)){

		int k=0;

		for(int i=1;i<=n;++i) k^=SG(read<int>());

		puts(k?"freda":"rainbow");

	}

	return 0;

}

相关文章