MATH PROBLEM PROGRESSION

数论

约数定理

Problem Statement : 找出不大于 $N$ 且恰好有 $9$ 个因数的正整数的个数。

题目要求求仅含9个因数的数字，我们由数论中的唯一分解定理可得：

所有自然数都可以表示为质数的乘积。

设 n $\in$ [1,N]。

一般的，一个数的因子都是$对称的$，这意味着a是n的因子，$\frac{a}{n}$也是n的因子，

而此时n有9个因子，说明n是$完全平方数$。

此时有:

$$ Divisors = \prod_{i=1}^k(a_i + 1)\space\space\space[N = \prod_{i=1}^kp_i^{a_i}] $$

此时我们得到了约数定理，n的约数个数d(n)即为:

$$ d(n) = (a_1 + 1)(a_2 + 1)(a_3 + 1)...(a_n + 1) $$

所以若一个数有9个因数，则我们可以得到两种情况：

其为某个质数的八次方，其9个因数分别为：($p^0,p^1,p^2,p^3,p^4 … p^8$)
其为某两个质数二次方的乘积，即($p_1^2*p_2^2$)

故此题的思路即为：

对$\sqrt{N}$以内的数进行线性筛，筛取素数。再根据单调性，用双指针试出所有质数(a,b)满足n=$a^2*b^2$,最后再暴力试出n = $p^8$计数即可。

时间复杂度O($\sqrt{N}lnln\sqrt{N}$)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void solve()
{
    Euler(1000000);
    int n;
    cin >> n;
    int ans = 0;
    for(int i : pri)
    {
        int res = qpow(i,8);
        if(res<=n) ans++;
        else break;
    }
    int len = pri.size();
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<i;j++)
        {
            int res = qpow(pri[i],2)*qpow(pri[j],2);
            if(res<=n) ans++;
            else break;
        }
    }
    cout << ans;
}

博弈论

Nim博弈

甲，乙两个人玩 Nim 取石子游戏。

Nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void solve()
{
    int n;
    int ans = 0;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x;
        ans ^= x;
    }
    if(ans==0)
    {
        cout << "No" << endl;
    }
    else cout << "Yes" << endl;
}

Bash博弈

游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（ $p$ 为质数，$k$ 为自然数，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在 October 先取，问她有没有必胜策略。若她有必胜策略，输出一行 October wins!；否则输出一行 Roy wins!。

1
2
3
4
5
6
7


void solve()
{
    int n;
    cin >> n;
    if(n%6) cout << "October wins!" << endl;
    else cout << "Roy wins!" << endl;
}

斐波那契博弈(Fibonacci Game + Zeckendorf定理)

有 $n$ 枚石子。两位玩家定了如下规则进行游戏：

Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
Mirko 在第一次取石子时可以取走任意多个；
接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


set<int> Fibonacci;
void pre()
{
    int last,cur,num;
    cur = 1;
    last = 1;
    Fibonacci.insert(1);
    while(cur < 1e15)
    {
        num = last + cur;
        last = cur;
        cur = num;
        Fibonacci.insert(cur);
    }
}
void solve()
{
    pre();
    int n;
    cin >> n;
    if(Fibonacci.find(n)!=Fibonacci.end())
    {
        cout << n;
        return;
    }
    while(n!=0)
    {
        auto it = lower_bound(Fibonacci.begin(),Fibonacci.end(),n);
        it--;
        n -= *it;
        if(Fibonacci.find(n)!=Fibonacci.end())
        {
            cout << n;
            return;
        }
    }
}

威佐夫博弈

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


const long double split = (long double)((sqrtl(5.0) + 1.0)/2.0); // 黄金分割率
void solve()
{
    int a,b;
    cin >> a >> b;
    int mx = max(a,b);
    int mn = min(a,b);
    if(mn != (int)((mx-mn)*split))
    {
        cout << 1;
        return;
    }
    else cout << 0;
}

SG函数及 SG定理

图游戏的概念：

任何局面都认为是图中的点，每一个局面都可以通过一种行动，走向图中的下一个点，如果当前行动有若干个，那么后继节点就有若干个。最终，必败局面的点认为不再有后继节点，那么公平组合游戏(ICG)，就可以对应成一张图

SG函数(Sprague-Grundy函数)

以下是SG返回值的求解方式，俗称MEX过程：

最终必败点是A，规定SG(A) = 0

假设状态点是B，那么SG(B) = 查看B所有后继节点的SG值，其中没有出现过的最小自然数SG(B) != 0,那么B为必胜态；SG(B) = 0,那么B为必败态。

SG定理(Bouton定理)

如果一个ICG游戏(总)，由若干个独立的ICG子游戏构成（分1，分2，分3…），那么：

$SG(总) = SG(分1)$ ^ $SG(分2)$ ^ $SG(分3)…$

任何ICG游戏都是如此，正确性证明类似尼姆博弈

题中是要善于使用对拍，打SG表观察等手段发现简洁规律。

Bash博弈 SG打表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


void solve()
{
    int n,m;
    // cin >> n >> m; // n个石头，一次可以取1~m个
    n = 15, m = 3;
    vector<int> sg(n+1); // sg[i]表示只剩i个石头的局面下，当前选手的状态(>0必胜=0必败)
    sg[0] = 0; // 没有石子剩余时必败
    vector<bool> appear(m+1,false); // 用于记录某个数是否出现过，用于得到MEX
    for(int i=1;i<=n;i++) // 遍历建立SG表
    {
        fill(appear.begin(),appear.end(),false);
        for(int j=1;j<=m and i-j>=0;j++)
        {
            appear[sg[i-j]] = true; // 表示当前节点其能连接到的状态下的sg值都是已知出现过的
        }
        // 更新sg[i]为MEX
        for(int p=0;p<=m;p++)
        {
            if(!appear[p]) 
            {
                sg[i] = p;
                break;
            }
        }
    }
    for(int i=0;i<=n;i++)
    {
        cout << "sg[" << i << "] == " << sg[i] << endl;
    }

}

得出SG表为：

INDEX	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
MEX	0	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3

显然当 n % (m+1) == 0 时，先手的SG值为0，此时处于必败态，否则则处于必胜态。

Nim博弈 SG定理

假如有 5 堆石子，1~5堆分别有 a b c d e 个石子，由于Nim博弈中可以取一堆石子中的任意数量，故他们的SG值分别为SG[a] = a, SG[b] = b …，则由SG定理得由这五个子游戏构成的Nim游戏的总SG值SG[总] = SG[a] ^ SG[b] ^ SG[c]…^ SG[e].

数论