1005 Lunch（nim博弈）

1005 Lunch
题意：给定

n

(

≤

10

)

n(\le10)

n(≤10)个数字

l

i

（

1

≤

l

i

≤

1

0

9

）

l_i（1\le l_i\le10^9）

li​（1≤li​≤109），两人分别选一个不等于1的数字进行拆分，假定选择的数字为

l

l

l,

k

k

k为他的因子，那么可以将他拆分成

l

k

\frac{l}{k}

kl​个

k

k

k。现在问先手是赢还是输。
思路：先后手必胜以及必败问题，感觉很博弈。考虑把拆分的问题转化成拿石子的问题。发现可拆分次数（因子次数和）可以相当于石子的个数。比如27：

27

⇒

3

∗

9

⇒

3

∗

3

⇒

3

∗

1

27\Rightarrow3*9\Rightarrow3*3\Rightarrow3*1

27⇒3∗9⇒3∗3⇒3∗1 (最多的拆分次数)

27

⇒

3

∗

9

⇒

9

∗

1

27\Rightarrow3*9\Rightarrow9*1

27⇒3∗9⇒9∗1

27

⇒

9

∗

3

⇒

3

∗

1

27\Rightarrow9*3\Rightarrow3*1

27⇒9∗3⇒3∗1

27

⇒

27

∗

1

27\Rightarrow27*1

27⇒27∗1

这样就可以把问题拆分成n堆式子，每次至少拿1个，也可以一次全部拿完。石子的个数就是

l

i

l_i

li​中的因子次数。nim博弈来了来了
注意点

对于因子2而言，无论2的幂次是多少，他的贡献只有1。可以这么思考，比如对于12而言，如果我拆成了两堆6，那么无论我在一堆中做什么操作，另外一个人都可以复制我的操作。也就是12与6是等效的。因为数字范围是

1

0

9

10^9

109，

1

≤

t

≤

2

∗

1

0

4

1\le t\le 2*10^4

1≤t≤2∗104,直接

n

\sqrt{n}

n
​进行分解是会t的。线性筛把

n

\sqrt{n}

n
​的素数分出来再进行唯一性分解。不要开LL！！！tle愉快^^

int v[maxn], prime[maxn];//v存质数，vis判断是不是质数

bool mp[maxn];

int primes(int n) {

	int m = 0;

	for (int i = 2; i <= n; i++) {

		if (v[i] == 0) {//i是质数

			v[i] = i; prime[++m] = i;

		}

		for (int j = 1; j <= m; j++) {

			if (prime[j] > v[i] || prime[j] > n / i)break;

			v[i*prime[j]] = prime[j];

		}

	}

	return m;

}

int cun[maxn], a[maxn];

int main()

{

	int n, m, ans, M;

	int t;

	sci(t);

	M=primes(50010);

	while (t--){

		sci(n);

		for (int i = 1; i <= n; i++)cun[i] = 0;

		for (int i = 1; i <= n; i++) {

			sci(a[i]);

			for (int j = 1; j <= M; j++) {

				if (a[i] == 1)break;

				if (prime[j] == 2&& a[i] % prime[j] == 0) {

					cun[i]++;

					while (a[i] % prime[j] == 0)

					{

						a[i] /= prime[j];

					}

					continue;

				}

				while (a[i]%prime[j]==0)

				{

					cun[i]++;

					a[i] /= prime[j];

				}

			}

			if (a[i] != 1)cun[i]++;

			if (i == 1)ans = cun[i];

			else ans ^= cun[i];

		}

		/*if (n == 1) {

			printf("W\n");

			continue;

		}*/

		if (ans)printf("W\n");

		else printf("L\n");

	}

	return 0;

}


原创：https://www.panoramacn.com

源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。
专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说


免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可->
联系客服
投诉资源
 www.panoramacn.com资源全部来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系站长并出示版权证明以便删除。
敬请谅解！ 侵权删帖/违法举报/投稿等事物联系邮箱：2640602276@qq.com
                
                
未经允许不得转载：书荒源码源码网每日更新网站源码模板！ » 2020CCPC网络赛-1005Lunch(nim 博弈)
                                
                                    
2020CCPC网络赛-1005Lunch(nim 博弈)
                                
                    

        

            
            
关注我们小说电影免费看
            
关注我们，获取更多的全网素材资源，有趣有料！
            
120000+人已关注
        
    
 
                
                    


                    
分享到：
        
                                赞(0)
        
                    打赏