自诚明，谓之性；自明诚，谓之教。诚则明矣，明则诚矣。

第四章 数论

一、 质数

定义： 在大于1的整数中，如果质包含1和本身这两个约数，就被称为质数或者素数

（1）质数的判定：试除法 O(sqrt(n))

1
2
3
4
5
6
7
8
9
bool is_prime(int n)
{
    if(n<2)  return false;
    for(int i = 2;i <= n / i;i++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

（2）分解质因数：试除法 最坏O(sqrt(n))

​ 性质：n中最多只包含一个大于sqrt(n)的质因子

1
2
3
4
5
6
7
8
9
10
11
12
13
void divide(int x)
{
    for(int i = 2;i <= x/i; i ++)
    {
        if(x % i == 0)
        {
            int s = 0;
            while(x % i == 0) x /= i,s++;
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x > 1) cout<<x<<' '<<1<<endl;
}

（3）朴素筛法求素数 O(loglog(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];             // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

（4）线性筛法求素数 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;  // primes[j] 一定是 i 的最小质因子
        }
    }
}

注：朴素筛法会出现一个数被重复筛，而线性筛法不会重复筛

二、约数

（1）试除法求所有约数

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

补充：对 二维 vector<int> 中第二个元素进行排序

1
2
3
4
5
static bool cmp(const vector<int>& a,const vector<int>& b)
{
    return a.back() < b.back();
}
sort(points.begin(),points.end(),cmp);

（2）约数个数 & 约数之和

1
2
3
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

（3）最大公约数 （辗转相除法）

核心 （a,b）= (b,a mod b)

证明：

首先易得 d|a , d|b 则d|ax + by

先证左边的公约数都是右边的公约数：已知 d = (a,b) => d|a , d|b , 又a mod b = a - [a/b]*b (下取整) <=>

a mod b = a - cb , 显然d｜a - cb , 所以d|b 且 d|a mod b

后证右边的公约数都是左边的公约数：已知 d|b , d|a mod b , 即d|a - cb => d|a - cb + cb =>d|a , 所以

d|a 且 d|b

1
2
3
4
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

三、欧拉函数

定义：

image-20221117142852275

欧拉函数

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围

1 ≤ n ≤ 100,
1 ≤ ai ≤ 2×10^9

输入样例：

1
2
3
4
3
3
6
8

输出样例：

1
2
3
2
2
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int x;
    while(n--)
    {
        cin>>x;
        int res=x;
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0)
            {
                res = res/i*(i-1);
                while(x%i==0) x/=i;
            }
        }
        if(x>1) res = res/x*(x-1);
        cout<<res<<endl;
    } 
    return 0;
}

筛法求欧拉函数

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围

1 ≤ n ≤ 10^6

输入样例：

1
6

输出样例：

1
12
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
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int p[N],cnt,phi[N];
int n,st[N];

long long get_eulers(int x){
    long long res=0;
    phi[1]=1;
    for(int i=2;i<=x;i++){
        if(!st[i]) {
            p[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;p[j]<=x/i;j++){
            st[p[j]*i]=true;
            if(i%p[j]==0){
                phi[p[j]*i]=p[j]*phi[i];
                break;
            }
            else phi[p[j]*i]=(p[j]-1)*phi[i];
        }
    }
    
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;
}

int main(){
    cin>>n;
    cout<<get_eulers(n)<<endl;

    return 0;
}
image-20221117144023571

四、快速幂

快速幂

给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 ai^bi mod pi 的值。

每个结果占一行。

数据范围

1 ≤ n ≤ 100000,
1 ≤ ai,bi,pi ≤ 2×10^9

输入样例：

1
2
3
2
3 2 5
4 3 9

输出样例：

1
2
4
1
image-20221118100800477 
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
#include <iostream>
#include <algorithm>
using namespace std;
typedef  long long LL;

LL qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    
    return res;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}

快速幂求逆元

image-20221118110453949 image-20221118110513343 image-20221118110534142 乘法逆元 
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
#include<iostream>
#include<algorithm>
using namespace std;
typedef  long long LL;

LL qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,p;
        cin>>a>>p;
        if(a%p) cout<<qmi(a,p-2,p)<<endl;
        else puts("impossible");
    }
    
    return 0;
}

五、扩展欧几里得算法

裴蜀定理：设a, b是不全为零的整数，则存在整数x, y，使得 ax + by = gcd(a, b)

扩展欧几里得算法

image-20221118174920130 exgcd 
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
#include<iostream>
using namespace std;

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;
        y=0;
    }
    else {
        exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b;
        int x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

倘若要求解d：

1
2
3
4
5
6
7
8
9
10
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

线性同余方程

image-20221118184849111 
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
#include<iostream>
using namespace std;

int exgcd(int a,int b,int &x,int &y){
    if(!b) {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b,m;
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d) puts("impossible");
        else cout<<(long long)x*(b/d)%m<<endl;
    }
    return 0;
}

六、中国剩余定理

表达整数的奇怪方式

image-20221119103520765 image-20221119103822894 表达整数的奇怪方式 
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
38
39
40
41
42
43
44
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b) {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main(){
    int n;
    cin>>n;
    LL a1,m1;
    cin>>a1>>m1;
    bool has_answer=true;
    for(int i=0;i<n-1;i++){
        LL a2,m2;
        cin>>a2>>m2;
        LL k1,k2;
        LL d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d){
            has_answer=false;
            break;
        }
        
        k1*=(m2-m1)/d;
        LL t=a2/d;
        k1=(k1%t+t)%t;
        m1=m1+a1*k1;
        a1=a1/d*a2;
    }
    
    if(has_answer) cout<<(m1%a1+a1)%a1<<endl;
    else puts("-1");
    return 0;
}

七、高斯消元

高斯消元解线性方程组

image-20221119130624401

高斯消元：

枚举每一列 c：

  • 找到绝对值最大的一行
  • 将该行换到最上面
  • 将该行第一个数变成1
  • 将改行下面所有行的第 c 列消成0

若最后有唯一解，则将原系数矩阵化为单位矩阵，第 n+1列即为解

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=110;
const double eps = 1e-8;
int n;
double a[N][N];

int gauss(){
    int c,r;
    for(c=0,r=0;c<n;c++){
        int t=r;
        for(int i=r;i<n;i++) {
            if(fabs(a[i][c])>fabs(a[t][c])) t=i;
        }
        
        if(fabs(a[t][c])<eps) continue;
        
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
        for(int i=n;i>=c;i--) a[r][i]/=a[r][c];
        for(int i=r+1;i<n;i++)
            if(fabs(a[i][c])>eps){
                for(int j=n;j>=c;j--){
                    a[i][j]-=a[r][j]*a[i][c];
                }
            }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++)
            if(fabs(a[i][n])>eps) return 0;
        return 2;
    }
    
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<n;j++)
            a[i][n]-=a[i][j]*a[j][n];
    
    return 1;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            cin>>a[i][j];
            
    int t=gauss();
    if(t==2) puts("Infinite group solutions");
    else if(t==1){
        for(int i=0;i<n;i++) {
            if(fabs(a[i][n])<eps) a[i][n]=0;
            printf("%.2lf\n",a[i][n]);
        }
    }
    else puts("No solution");
    return 0;
}

高斯消元解异或线性方程组

image-20221123102748482 
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 类比高斯消元解线性方程组
#include<iostream>
using namespace std;
const int N=110;
int a[N][N],n;

int gauss(){
    int r,c;
    for(r=c=0;c<n;c++){
        int t=r;
        for(int i=r;i<n;i++){
            if(a[i][c]){
                t=i;
                break;
            }
        }
        if(!a[t][c]) continue;
        for(int i=c;i<n+1;i++) swap(a[r][i],a[t][i]);
        for(int i=r+1;i<n;i++){
            if(a[i][c]){
                for(int j=c;j<n+1;j++)
                    a[i][j]^=a[r][j];
            }
        }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++)
            if(a[i][n]) 
                return 2;
        return 1;
    }
    
    for(int i=n-1;i>=0;i--)
    {
        for(int j=i+1;j<n+1;j++){
            if(a[i][j]) a[i][n]^=a[j][n];
        }
    }
    
    return 0;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n+1;j++){
            cin>>a[i][j];
        }
    }
    
    int t=gauss();
    if(t==1) puts("Multiple sets of solutions");
    else if(t==2) puts("No solution");
    else {
        for(int i=0;i<n;i++) cout<<a[i][n]<<endl;
    }
    return 0;
}

八、求组合数

求组合数 I

image-20221121091257886 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
const int N = 2010, mod = 1e9+7;
int c[N][N];
int main()
{
    int n;
    cin>>n;
    //预处理
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    
    for(int i=0;i<n;i++)
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}

求组合数 II

image-20221121091405083 求组合数II 
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
#include<iostream>
using namespace std;
const int N=100010,mod=1e9+7;
typedef long long LL;
int fact[N],infact[N];

int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
        
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        cout<<(LL)fact[a]*infact[a-b]%mod*infact[b]%mod<<endl;
    }
    
    return 0;
}

求组合数 III

image-20221121100052853 image-20221121104902712 
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
38
39
40
#include<iostream>
using namespace std;
typedef long long LL;

int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

int C(int a,int b,int p){
    if(!b) return 1;
    int res=1;
    for(int i=1,j=a;i<=b;i++,j--){
        res=(LL)res*j%p;
        res=(LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}

int lucas(LL a,LL b,int p){
    if(a<p && b<p) return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        LL a,b;
        int p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}

求组合数 IV

适用于结果很大，没有取模时

image-20221121105358138 求组合数 IV 
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=5010;
int primes[N],cnt;
int st[N];
int sum[N];

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int get(int a,int p){
    int res=0;
    while(a){
        res+=a/p;
        a/=p;
    }
    return res;
}

vector<int> mul(vector<int> &A,int b){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++){
        t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(t){
        C.push_back(t%10);
        t/=10;
    }
    return C;
}

int main(){
    int a,b;
    cin>>a>>b;
    get_primes(a);
    
    
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }
    
    vector<int> C;
    C.push_back(1);
    
    for(int i=0;i<cnt;i++){
        for(int j=0;j<sum[i];j++){
            C = mul(C,primes[i]);
        }
    }
    
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    
    return 0;
}

卡特兰数

image-20221122140423709

满足条件的01序列

给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

输出的答案对 10^9+7 取模。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示答案。

数据范围

1 ≤ n ≤ 10^5

输入样例：
1
3
输出样例：
1
5

image-20221122140927730

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
#include<iostream>
using namespace std;
typedef long long LL;
const int mod=1e9+7;

int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    int a=2*n,b=n;
    
    int res=1;
    for(int i=1,j=a;i<=b;i++,j--){
        res=(LL)res*j%mod;
        res=(LL)res*qmi(i,mod-2,mod)%mod;
    }
    res=(LL)res*qmi(n+1,mod-2,mod)%mod;
    cout<<res<<endl;
    
    return 0;
}

九、容斥原理

能被整除的数

image-20221122154310590 image-20221122154426665 
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
38
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 20;
int p[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i++) {
        int t = 1;             //选中集合对应质数的乘积
        int s = 0;             //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j++){
            //选中一个集合
            if(i >> j & 1){
                //乘积大于n, 则n/t = 0, 跳出这轮循环
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;
                }
                s++;                  //有一个1，集合数量+1
                t *= p[j];
            }
        }

        if(t == -1) continue;  
        if(s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
        else res -= n / t;                      //反之则为 -1
    }
    cout << res << endl;
    return 0;
}

十、博弈论

Nim游戏

image-20221122164519962

image-20221122164443116 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int n;
int main(){
    cin>>n;
    int res=0;
    while(n--){
        int x;
        cin>>x;
        res^=x;
    }
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

台阶-Nim游戏

image-20221123135716400 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(i&1) res^=x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

集合-Nim游戏

image-20221123093035221 image-20221123093256842

参考题解：https://www.acwing.com/solution/content/23435/

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值

int sg(int x)
{
    if(f[x]!=-1) return f[x];
    //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
    set<int> S;
    //set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
    for(int i=0;i<m;i++)
    {
        int sum=s[i];
        if(x>=sum) S.insert(sg(x-sum));
        //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
    }

    for(int i=0;;i++)
    //循环完之后可以进行选出最小的没有出现的自然数的操作
     if(!S.count(i))
      return f[x]=i;
}

int main()
{
    cin>>m;
    for(int i=0;i<m;i++)
    cin>>s[i];

    cin>>n;
    memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过

    int res=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res^=sg(x);
        //观察异或值的变化,基本原理与Nim游戏相同
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

拆分-Nim游戏

image-20221123134733494 image-20221123134710261 
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
38
39
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
const int N=110;
int f[N],n;

int sg(int x){
    if(f[x]!=-1) return f[x];
    
    set<int> S;
    for(int i=0;i<x;i++){
        for(int j=0;j<=i;j++){
            S.insert(sg(i)^sg(j));
        }
    }
    
    for(int i=0; ; i++){
        if(!S.count(i)){
            f[x]=i;
            return f[x];
        }
    }
}

int main(){
    cin>>n;
    int res=0;
    memset(f,-1,sizeof f);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}