C - Win or Freeze

1.思路

　　题目给定一个数，两个人轮流操作：把这个数换成他的非平凡因数，如果有个人不能操作了，那么这个人就赢了。输出第几个人胜利，如果第一个人胜利，则还要输出它的第一次操作。如果我制造出一个只有两个质数的数，这样对手只能取走其中一个，然后我走不动了，我就赢了，特判n为1。

2.代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn = 2e5 + 5;
 5 ll n;
 6 ll a[maxn];
 7 int cnt;
 8 bool judge(ll x) {
 9     for(ll i = 2; i * i <= x; i++) {
10         if(x % i == 0) {
11             return false;
12         }
13     }
14     return true;
15 }
16 void fenjie(ll x) {
17     for(ll i = 2; i * i <= x; i++) {
18         if(x % i == 0 && judge(i)) {
19             while(x % i == 0) {
20                 a[++cnt] = i;
21                 x /= i;
22             }
23         }
24         if(cnt >= 2) {
25             break;
26         }
27     }
28     if(x > 1) {
29         a[++cnt] = x;
30     }
31 }
32 int main() {
33     cin >> n;
34     if(n == 1 || judge(n)) {
35         cout << 1 << endl << 0 << endl;
36         return 0 ;
37     }
38     fenjie(n);
39     if(cnt == 2 && a[1]*a[2] == n) {
40         cout << 2 << endl;
41     } else {
42         cout << 1 << endl;
43         printf("%lld\n", a[1] * a[2]);
44     }
45     
46     return 0 ;
47  }

View Code