Project Euler 509

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

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 $1 \le a, b, c \le n$.

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

Find $S(123456787654321)\text{ modulo }1234567890$.

解决方案

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

只拿一堆石头时，不难写出$sg(n)$为：

其中运算$\text{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$使得$2^k\mid n$。

那么不难计算得到，$1\sim N$中有$\left\lfloor\dfrac{N}{2^i}\right\rfloor-\left\lfloor\dfrac{N}{2^{i+1}}\right\rfloor$个数，其$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);
}