【质因数分解+简单博弈】Win or Freeze CodeForces - 150A

蔚落 2022-06-04 01:43 163阅读 0赞

Think:  
1知识点：质因数分解+简单博弈  
2题意：  
（1）：输入一个数n(n <= 1e13)，开局，A选择n的一个因数(非１和非n)代替n，紧接着B选择当前已被替换的n的一个因数(非１和非当前n)代替当前n，即不断更新n，直至n无法分解，此时无法分解的选手赢  
（2）：若A赢则输出1和任意一个先选择可得到A赢的数；若B赢则只输出2  
3思路分析：  
（1）：简单博弈分析，若X先得到两个质数的乘积即下下局无法分解，则X必赢  
（2）：如何判断谁先得到两个数的乘积？将n进行质因数分解，若只有2个质因子，则表明A必输，若有1个质因子，则A赢，若有多余两个质因子，则表明只要A选择任意两个质因子的乘积，则下下局必定无法分解，即A必赢  
（3）：注意n == 1时需要特别判断

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    typedef long long LL;
    
    int tp;
    LL link[104];
    
    int main(){
        LL n;
        while(cin >> n){
            if(n == 1){
                printf("1\n");
                printf("0\n");
                continue;
            }
            tp = 0;
            for(LL i = 2; i <= sqrt(n); i++){
                while(n%i == 0){
                    link[tp++] = i;
                    n /= i;
                }
            }
            if(n != 1) link[tp++] = n;
            if(tp == 1){
                printf("1\n");
                printf("0\n");
            }
            else if(tp == 2){
                printf("2\n");
            }
            else {
                printf("1\n");
                printf("%lld\n", link[0]*link[1]);
            }
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/CodeForces-150A