C - Number Game
比赛的时候,此题%2写成了%i,然后就。。。
题解:博弈论
假设这个数给出的是奇数,那么我们可以直接给A赢
如果是偶数呢,那么我们就需要看看她有没有基数因子。
如果奇数因子只有一个,那么我们需要看他可以除以几个2,假设只可以除以一个2,那么我们即便除了这唯一的一个奇数因子,得到的答案是2,那么是F赢。
如果奇数因子有多个呢,那么A必然赢。不妨可以这样想,如果这个数只可以除以一个2,那么我们就除以n-1个奇数因子,让他变成第一种情况的状态,A赢,如果可以除以多个2呢,那么我们把所有的奇数因子除掉,让F无法除以奇数,只能被迫减一,还是A赢。
要特别注意如何找奇数因子个数!
/*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1010; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int mod = 100000000; using namespace std; const double pi = acos(-1); int cnt1,cnt2; int judge(int n){ int cnt=0; for(int i=2;i*i<=n;i++){ if(i%2==1&&n%i==0) cnt++; if(i%2==0&&n%i==0){ if((n/i)%2==1) cnt++; } } return cnt; } int main() { int t; cin>>t; while(t--){ int x; cin>>x; cnt1=cnt2=0; bool flag=false; if(x%2==1&&x!=1){ cout<<"Ashishgup"<<endl; } else if(x==1){ cout<<"FastestFinger"<<endl; } else if(x==2) cout<<"Ashishgup"<<endl; else{ cnt1=judge(x); //cout<<cnt1<<endl; if(cnt1==0) cout<<"FastestFinger"<<endl; else if(x%4==0&&cnt1>=1) cout<<"Ashishgup"<<endl; else if(x%4!=0&&cnt1>1) cout<<"Ashishgup"<<endl; else cout<<"FastestFinger"<<endl; } } return 0; }