2022河南萌新联赛第（一）场：河南工业大学 A - Alice and Bob

我们可以对 n n n 进行质因数分解，那么其实就是把 n n n 分成了一些石子，对于每个素因数 p p p 都看作一堆石子，那么每次操作转化为从某堆石子拿走一些石子，那么就转化为 A n t i − N i m Anti−Nim Anti−Nim 博弈。

根据 A n t i − N i m Anti−Nim Anti−Nim 游戏结论，当且仅当所有堆石子数等于 1 1 1 并且所有堆石子数量异或和为 0 0 0 (有偶数堆)或者存在一堆石子数大于 1 1 1 并且所有堆石子数量异或和大于 0 0 0 先手必胜；反之必败。所以先分解质因数，然后使用 A n t i − N i m Anti−Nim Anti−Nim 博弈。

时间复杂度为 O ( n ) O(sqrt n) O(n ​)

#include
using namespace std;

int main()
{
	long long n;cin>>n;
	
	int ans=0,ok=0;
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
		{
			int cnt=0;
			while(n%i==0) n/=i,cnt++;
			if(cnt!=1) ok=1;
			ans^=cnt;
		}
	if(n>1) ans^=1;
	
	if((ok && ans) || (!ok && !ans)) cout<<"Alice win"<
                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！