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