Codeforces Round 651 (Div. 2)C. Number Game(数学思维数论)

发布时间:2023年12月22日

C. Number Game
我们考虑那些状态是必胜态

  1. 我的回合时n为奇数(除1外),直接除以n则必胜
  2. 下面偶数的情况稍复杂
    • 偶数我们能进行的操作只有除以一个奇数,需要考虑怎么把当前状态变为对手的必败态
    • 偶数一定含2的因子, n = 2 k ? q , q 为奇数 n=2^k*q,q为奇数 n=2k?q,q为奇数
    • k = 1 时如果 q k=1时如果q k=1时如果q是一个质数那么只能除一次q这样的话,对手就会得到2我们就必败,如果q不是质数就可以进行质因数分解,我们只留下最小的一个质因数,其余的都是我们本次操作要除掉的数,也就是对手会得到 2 ? q , 其中 q 为质数,这样对手就进入了必败态 2*q,其中q为质数,这样对手就进入了必败态 2?q,其中q为质数,这样对手就进入了必败态
    • k > 1 时 n = 2 k ? q 我们只需要把 q 除掉,剩下 2 k 为必败态因为没有奇因子 k>1时n=2^k*q我们只需要把q除掉,剩下2^k为必败态因为没有奇因子 k>1n=2k?q我们只需要把q除掉,剩下2k为必败态因为没有奇因子只能-1变为奇数

综上我们就讨论完了所有情况
代码有点丑写的

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 1e7+10;
int t; 
int primes[N], cnt[N], m;
void solve()
{
	int n; cin >> n;
	rep(i,1,m)	primes[i]=0, cnt[i]=0;
	if(n==1)
	{
		cout << "FastestFinger" << endl;
		return;	
	}
	if(n==2||n%2==1)
	{
		cout << "Ashishgup" << endl;
		return;
	}
	m=0;
	rep(i,2,n/i)
	{
		if(n%i==0)
		{
			primes[++m]=i;
			while(n%i==0)	
			{
				cnt[m]++;
				n/=i;	
			}
		}
	}	
	if(n>1)
	{
		primes[++m]=n;
		cnt[m]=1;
	}
	int num2=0, other=0; 
	rep(i,1,m)
	{
		if(primes[i]==2)	num2+=cnt[i];
		else	other+=cnt[i];
//		cout<<primes[i]<<' '<<cnt[i]<<endl;
	}
	if(num2==1)
	{
		if(other>=2)	
		{
			cout << "Ashishgup" << endl;
			return;
		}
		else
		{
			cout << "FastestFinger" << endl;
			return;
		}
	}
	else
	{
		if(other>=1)
		{
			cout << "Ashishgup" << endl;
			return;
		}
		else
		{
			cout << "FastestFinger" << endl;
			return;
		}
	}
	cout << "FastestFinger" << endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
	cin >> t;
	while(t --)	
	solve();
	return 0;
}
文章来源:https://blog.csdn.net/weixin_61426225/article/details/135150904
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。