51nod 1755 除数游戏(博弈)

1.0 秒 131,072.0 KB 20 分 3级题

在除数游戏中,两人轮流行动,初始时有一个整数q,每次行动要写下一个整数,这个整数必须是最近一次出现的整数的“强除数”。所谓一个整数的“强除数”是指除了1和该整数本身以外,可以整除该整数的整数。

当游戏的某一方找不出符合以上条件的整数时,该方取得胜利,游戏结束。

假设游戏双方都采取最好的策略,给出初始数字。计算第一个写数字的人赢,还是第二个写数字的人赢。

样例解释:

在样例一中,数字6的“强除数”是2和3。不管是写哪个数字,下一个人都赢了。
在样例二中,6是30的一个“强除数”。写下6后,接下来的过程同上。


看因数个数,如果上来就是质数那么1赢,一个因数那1取完1赢,两个因数的话就2赢,两个以上因数不管怎么取最后决定奇偶的权利都在1手中,都是1赢

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;

#define LL long long
int main(){
LL n,m;
cin>>n;
m=n;
int ji=0;
for(LL i=2;i*i<=n;i++){
while(m%i==0){
m/=i;
ji++;
}
if(ji>2)break;
}
if(m>1)ji++;
if(ji==2)puts("2");
else puts("1");
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信