51Nod 1755 除数游戏

Problem

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

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

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

样例解释：

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

Solution

分解，1个因数1赢，2个2赢，再往上1写到两个，1赢。

Code

#include<stdio.h>
#define ll long long
ll n,x;
int s;
int main(){
	//prime();
	scanf("%lld",&n);
	x=n;
	for(ll i=2;i*i<=x;i++){
		while(n%i==0){
			n/=i;
			s++;
		}
		if(s>=3) break;
	}
	if(n>1) s++;
	if(s==2){
		printf("2\n");
	}
	else{
		printf("1\n");
	}
	return 0;
}