Project Euler 509

Project Euler 509

题目

Divisor Nim

Anton and Bertrand love to play three pile Nim.

However, after a lot of games of Nim they got bored and changed the rules somewhat.

They may only take a number of stones from a pile that is a proper divisor of the number of stones present in the pile.

E.g. if a pile at a certain moment contains 24 stones they may take only 1,2,3,4,6,8 or 12 stones from that pile.

So if a pile contains one stone they can't take the last stone from it as 1 isn't a proper divisor of 1.

The first player that can't make a valid move loses the game. Of course both Anton and Bertrand play optimally.

The triple (a,b,c) indicates the number of stones in the three piles.

Let S(n) be the number of winning positions for the next player for 1a,b,cn.

S(10)=692 and S(100)=735494.

Find S(123456787654321) modulo 1234567890.

解决方案

在每一次操作中,一方可以拿起三堆石头 (a,b,c) 的其中一堆的石头的因数个。并且这 3 堆石头是相互独立的。因此,三堆石头的 sg 函数 sg(a,b,c)=sg(a)sg(b)sg(c). 那么此时只需要单独考虑一堆石头的情况 sg(n)

只拿一堆石头时,不难写出 sg(n) 为:

sg(n)={0ifn=1mex({sg(nd)|(dn)dn})else

其中运算 mex(s) 表示集合 s 中未出现的最小的非负整数。

那么通过以下程序暴力打印出一部分数的 sg 函数值,在 OEIS 中查询后结果为 A007814

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;
const int N=100,M=100;
int sg[N+4];
bool mex[M+4];
int main(){
sg[1]=0;
for(int i=2;i<=N;i++){
memset(mex,0,sizeof(mex));
vector<ll>d=divisors(i);
d.pop_back();
for(ll x:d)
mex[sg[i-x]]=1;
int j=0;
for(;mex[j];++j);
sg[i]=j;
printf("%d %d\n",i,sg[i]);
}
}

这个数列说明 sg(n) 是最大的正整数 k 使得 2kn

那么不难计算得到,1N 中有 N2iN2i+1 个数,其 sg 函数值为 i

因此,最终直接三重循环枚举 sg 值,直接求个数之积的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=123456787654321;
const int M=60;
ll cnt[M+4],mod=1234567890;
int main(){
for(int i=0;i<=M;i++)
cnt[i]=((N>>i)-(N>>(i+1)))%mod;
ll ans=0;
for(int i=0;i<=M;i++)
for(int j=0;j<=M;j++)
for(int k=0;k<=M;k++)
if(i^j^k) ans=(ans+cnt[i]*cnt[j]%mod*cnt[k])%mod;
printf("%lld\n",ans);
}