1 条题解

  • 0
    @ 2024-11-23 19:31:27

    思路

    xiaomao n=1n=1 获胜, n=2xn=2^x 其中 ( x>1x>1 ) 和 n=2pn= 2 \cdot p 其中 pp 是素数 3\ge 3 否则 Jerry_seven 获胜。

    证明

    让我们来分析以下 33 种情况:

    • 情况 11 : n 是奇数 这里 Jerry_seven 可以用 nn 除以它自己,因为它是奇数,因此是 n/n=1n / n = 1 ,而 xiaomao 输了。这里 n=1n = 1 是个例外。
    • 情况 22nn 是偶数,并且没有大于 11 的奇数除数。 这里的 nn2x2^x 的形式。由于 nn 没有大于 11 的奇数除数,所以 Jerry_seven 不得不减去 11 使 nn 成为奇数。因此,如果是 x>1x > 1xiaomao 获胜。对于 x=1x = 1n1n - 1 等于 11 ,因此 Jerry_seven 获胜。
    • 情况 33nn 是偶数且有奇数除数 如果 nn 可以被 44 整除,那么 Jerry_seven 可以将 nn 除以最大的奇数因子,之后 nn 变成 2x2^x 的形式,其中 x>1x \gt 1 是奇数,因此 Jerry_seven 获胜。 否则 nn 必须是 2p2 \cdot p 的形式,其中 pp 是奇数。如果 pp 是素数,那么 Jerry_seven 就输了,因为他可以将 nn 减去 11 或除以 pp ,而这两种方法都会让他输掉。如果 pp 不是质数,那么 pp 必须是 p1p2p_1 \cdot p_2 的形式,其中 p1p_1 是质数,而 p2p_2 是任何奇数 >1\gt 1Jerry_seven 可以用 nn 除以 p2p_2 来获胜。

    代码

    #include <bits/stdc++.h>
    using namespace std;
    
    #define int long long 
    #define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    
    int IsPrime(int n) {
        if(n < 2) return false;
        for(int i = 2; i <= sqrt(n); i ++) {
            if(n % i == 0) return 0;
        }
        return 1;
    }
    
    void solve() {
        int n;
        cin >> n;
        if(n == 1) cout << "xiaomao" << endl;
        else if(n == 2) cout << "Jerry_seven" << endl;
        else {
            if(n & 1) cout << "Jerry_seven" << endl;
            else {
                int cnt = 0;
                while(n) {
                    n /= 2;
                    cnt ++;
                    if(n & 1) break;
                }
                if(n == 1) cout << "xiaomao" << endl;
                else if(IsPrime(n)) {
                    if(cnt == 1) cout << "xiaomao" << endl;
                    else cout << "Jerry_seven" << endl;
                }
                else cout << "Jerry_seven" << endl;
            }
        }
    }
    
    signed main() {
        FastIO;
    
        int _T_ = 1;
        cin >> _T_;
    
        while(_T_ --) solve();
        return 0;
    }
    
    • 1

    信息

    ID
    1080
    时间
    2000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    26
    已通过
    3
    上传者