2020CCPC网络赛-1005Lunch(nim 博弈)


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系列小说

2020CCPC网络赛-1005Lunch(nim 博弈)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 2020CCPC网络赛-1005Lunch(nim 博弈)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏