Number Game

Created by LXC on Tue Mar 5 15:59:43 2024

https://codeforces.com/problemset/problem/1370/C

ranting: 1400

tag: games, math, number theory

problem

有一个正整数 $n$。

两名玩家轮流操作。每次操作可以执行以下一种：

• 将 $n$ 除以一个 $n$ 的大于 $1$ 的奇数因子。
• 将 $n$ 减去 $1$（若 $n\gt1$）。

无法操作者输。

问先手是否有必胜策略。如果先手有必胜策略，输出 Ashishgup ，否则输出 FastestFinger 。

多组数据，数据组数 $t \leq 100$，$1 \leq n \leq 10^9$

翻译 by Meatherm

solution

谁面对数字1,谁就输了。

对于一个奇数，谁先手谁就赢了。

对于一个偶数，如果是2,就直接赢了，否则如果抽离掉所有奇数因子后剩下是2,那么就留下一个奇数因子，不然就只留下偶数因子，然后丢给对面。所以只要这个偶数不是 大于2的2的幂次 或者 2乘以一个质数，那就必赢。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

int check(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    if (n%2) return 1;
    if (n == (n&-n)) return 0;
    if ((n&-n) == 2) {
        n/=2;
        for (int i=3; i*i<=n; i+=2) {
            if (n%i == 0) return 1;
        }
        return 0;
    }
    return 1;
}

void sol() {
    int n;
    cin >> n; 
    if (check(n)) {
        cout << "Ashishgup" << "\n";
    } else {
        cout << "FastestFinger" << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}