数学知识

[toc]

算数基本定理

任何大于 1 的整数是质数或独一无二的质数乘积（不理次序）。

任何一个大于1的自然数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
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve(int n) {
  vector<int> vec;
  for (int i = 1; i <= n / i; i++) {
    if (n % i == 0)
      {
        vec.push_back(i);
        if (i != n / i)
            vec.push_back(n / i);
      }
    
  }
  sort(vec.begin(),vec.end());
    for(auto i : vec)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
  int n;
  cin >> n;
  while(n --)
  {
    int x;
    cin >> x;
    solve(x);
  }
 
}

870. 约数个数

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
#include <iostream>
#include <unordered_map>

using namespace std;

long long mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  unordered_map<int, int> cnt;
  while (n--) {
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i++) {
      while (x % i == 0) {
        x /= i;
        cnt[i]++;
      }
    }
    if (x > 1)      //n也是一个质因子
      cnt[x]++;
  }
  long long ans = 1;
  for (auto c : cnt) {
       //res = (x1+1)(x2+1)(x3+1)…(xk+1)
    ans = ans * (c.second + 1) % mod;
  }
  cout << ans << endl;
}

871. 约数求和

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
#include <iostream>
#include <unordered_map>

using namespace std;
#define LL long long
long long mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  unordered_map<int, int> cnt;
  while (n--) {
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i++) {
      while (x % i == 0) {
        x /= i;
        cnt[i]++;
      }
    }
    if (x > 1)      //n也是一个质因子
      cnt[x]++;
  }
  long long res = 1;

    for (auto p : cnt)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        //t = 1   t = p + 1   t = p^2 + p + 1
        res = res * t % mod;
    }

    cout << res << endl;



  cout << ans << endl;
}

872. 最大公约数

欧几里得算法（辗转相除法）：

(a， b) = (a % b， b) = （b, a %b）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;


int gcd(int a, int b)
{
    return b == 0? a : gcd(b, a % b);
}


int main()
{
    int n, a, b;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        cout << gcd(a,b) << endl;
    }
}

欧拉函数

873. 欧拉函数

如果 (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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

using namespace std;
const int  N = 100010;

typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    int res = n;
    for(int i = 2; i <= n / i; i++)
    {
        if(n % i == 0)
        {
            
            // res*=(p - 1) / p
            res = res / i * (i - 1);
            while(n % i == 0)   //对n约分
            {
                n /= i;
            }
        }
    }
    // 如果有剩余，则剩余是个质因子
    if(n > 1)
    {
        res = res / n * (n - 1);
    }
    cout <<res << endl;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        solve();
    }
}


874. 筛法求欧拉函数

AcWing 874. 筛法求欧拉函数 - AcWing

AcWing 874. 筛法求欧拉函数 - AcWing

phi[primes[j] i]分为两种情况：
① i % primes[j] == 0时：primes[j]是i的最小质因子，也是primes[j] i的最小质因子，因此1 - 1 / primes[j]这一项在phi[i]中计算过了，只需将基数N
𝑁
修正为primes[j]倍，最终结果为phi[i] primes[j]。
② i % primes[j] != 0：primes[j]不是i的质因子，只是primes[j] i的最小质因子，因此不仅需要将基数N
𝑁
修正为primes[j]倍，还需要补上1 - 1 / primes[j]这一项，因此最终结果phi[i] * (primes[j] - 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
60
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1000010;

int primes[N], cnt;
int phi[N];
bool st[N];

void get_eulers(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) {
      primes[cnt++] = i;
      phi[i] = i - 1; // 若为质数，有i - 1个数与其互质
    }
    for (int j = 0; primes[j] <= n / i; j++) {
      st[primes[j] * i] = true;
      if (i % primes[j] == 0) //最小质因子
      {
        phi[primes[j] * i] = phi[i] * primes[j];
        /*
  当p[j]是i的一个约数时,i的质因数与p[j]*i的质因数完全相同。
  i      = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^ap[j])...(pk^ak)
  i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^(ap[j]+1))...(pk^ak)
  由欧拉函数的定义可知：
  Φ(i)      =  i   * (1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
  Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
  */
        break;
      }
      /*
当i%p[j]!=0时，p[j]不是i的约数，i与i*p[j]的质因子相差一个p[j]
i      = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)
i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)*(p[j]^ap[j])
所以由欧拉函数的定义可知：
Φ(i)      =  i    *(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)
Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)(1-1/p[j])
*/
      phi[primes[j] * i] = phi[i] * (primes[j] - 1);
    }
  }
}

int main() {
  int n;
  cin >> n;

  get_eulers(n);

  LL res = 0;
  for (int i = 1; i <= n; i++)
    res += phi[i];
  printf("%lld\n", res);

  return 0;
}

欧拉定理

欧拉定理是数论中的一个重要定理，它描述了在模 (m) 的整数环中，与 (m) 互质的整数 (a) 和 (m) 的欧拉函数 (\varphi(m)) 之间的关系。以下是欧拉定理的表述：
如果 (m) 是一个正整数，(a) 是一个与 (m) 互质的正整数，那么 (a^{\varphi(m)} \equiv 1 \pmod{m})。
其中，(\varphi(m)) 表示小于或等于 (m) 的与 (m) 互质的正整数的个数，这个函数被称为欧拉函数。
以下是欧拉定理的Markdown格式表示：

1
2
3
4
5
# 欧拉定理
欧拉定理是数论中的一个基本定理，其内容如下：
如果 \( m \) 是一个正整数，\( a \) 是一个与 \( m \) 互质的正整数，那么：
\[ a^{\varphi(m)} \equiv 1 \pmod{m} \]
这里，\(\varphi(m)\) 是欧拉函数，表示小于或等于 \( m \) 的与 \( m \) 互质的正整数的个数。

当你将上述Markdown文本放入支持Markdown的编辑器中时，它将被渲染为格式化的文本，如下所示：

欧拉定理和费马丁柳

欧拉定理：
如果 ( m ) 是一个正整数，( a ) 是一个与 ( m ) 互质的正整数

那么：

费马小定理:
如果 ( p ) 是一个素数（有p-1个数与其互质），而 ( a ) 是一个不被 ( p ) 整除的整数，那么：

快速幂

875. 快速幂

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
#include <iostream>

using namespace std;

typedef long long LL;                            



int qmi(int a, int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;		//注意转型，因为我们传入的类型为int
        k = k >> 1;
        //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
        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;
    }    
}

876. 快速幂求逆元

费马定理+快速幂 [AcWing 876. 快速幂求逆元 - AcWing](https://www.acwing.com/solution/content/3054/) a / b ≡ a * x (mod n) 两边同乘b可得 a ≡ a * b * x (mod n) 即 1 ≡ b * x (mod n) 同 b * x ≡ 1 (mod n) 由费马小定理可知，当n为质数时 b ^ (n - 1) ≡ 1 (mod n) 拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n) 故当n为质数时，b的乘法逆元 x = b ^ (n - 2) 
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
#include <iostream>

using namespace std;

typedef long long LL;                            

//a^k%p
int qmi(int a, int k, int p)
{
    LL 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;
    while(n--)
    {
        int a, p;
        cin >> a >> p;
        int res = qmi(a, p - 2, p);
        if(a % p)  cout << res << endl;	//互质存在逆元
        else cout <<"impossible"<< endl;
    }
}

拓展欧几里得算法

容斥原理

并集

交集

共有

种情况

即——对于集合个数与符号的关系，奇数符号为正，偶数符号为负

AcWing 890. 能被整除的数

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

typedef long long LL;

const int N = 20;

int p[N];

int main() {
    int n, m;
    cin >> n >> m;

    // 输入 m 个质数
    for (int i = 0; i < m; i++) {
        cin >> p[i];
    }

    int res = 0;

    // 枚举所有可能的质数组合 ，所有组合数和为2^n
    for (int i = 1; i < 1 << m; i++) {
        int product = 1, count = 0;
        //质数乘积，count表示包含几个集合

        // 检查当前子集是否包含第 j 个质数
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) {
                // 如果乘积超过 n，跳过当前子集
                if ((LL)product * p[j] > n) {
                    product = -1;
                    break;
                }
                product *= p[j];    //并集大小
                count++;    //集合个数++
            }
        }

        // 根据容斥原理更新结果
        if (product != -1) {
            if (count&1) {      //奇数个集合，符号为正
                res += n / product;
            } else {            //偶数个集合，符号为负
                res -= n / product;
            }
        }
    }

    cout << res << endl;

    return 0;
}

博弈论

公平组合游戏（NIM游戏）

公平组合游戏（Impartial Game）的定义如下：

  • 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
  • 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
  • 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
  • 异或和为0：当前玩家处于必败态，无论怎么操作，对手总能迫使你回到必败态。
  • 异或和非0：当前玩家处于必胜态，存在一种操作使对手进入必败态。

SG函数

  1. SG值为0：如果 SG(G)=0SG(G)=0，则当前状态是必败态（P-position），即当前玩家无法必胜。
  2. SG值不为0：如果 SG(G)≠0SG(G)\=0，则当前状态是必胜态（N-position），即当前玩家可以通过策略将游戏转移到必败态。
  3. SG函数理论多个独立局面的SG值，等于这些局面SG值的异或和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
memset(f,-1,sizeof(f));
f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值


int sg(int x) {
    if (f[x] != -1) return f[x];  // 记忆化：已计算过则直接返回
    set<int> S;                   // 存储当前状态x的所有后继状态的SG值，用set去重
    // 遍历所有合法操作（s数组为允许的取法集合，如每次可取1、2、3个石子）
    for (int i = 0; i < m; i++) { 
        int sum = s[i];           // 当前允许取的石子数（如s[i]=1,2,3）
        if (x >= sum) 
            S.insert(sg(x - sum)); // 递归计算后继状态x-sum的SG值
    }
    // 计算Mex：找最小的未出现在S中的自然数
    for (int i = 0; ; i++) 
        if (!S.count(i)) 
            return f[x] = i;      // 保存并返回当前状态的SG值
}

AcWing 891. Nim游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> n;
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for(int i = 0; i < n; i++)
    {
        res ^= arr[i];
    }
    if(res == 0)
    {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}

AcWing 892. 台阶-Nim游戏

分为奇数阶和偶数阶

  • 对于偶数阶，若存在某偶数级台阶石子数影响胜负，则玩家可将其移动到下一级奇数级台阶，改变奇数级异或和。但对手可立即将这些石子继续传递到后续台阶，最终消除其对奇数级异或和的影响。

  • 对于奇数阶，则是由这些奇数台阶石子堆组成的经典Nim游戏问题。所有石子都可以通过偶数次操作（还是先手）转化到一阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    int res = 0;
    for(int i = 0; i < n; i+=2)
    {
        res ^= arr[i];
    }
    if(res == 0)
    {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}

AcWing 893. 集合-Nim游戏

SG的核心作用是将复杂的博弈问题转化为等效的 Nim游戏

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
#include <cstring>
#include <iostream>
#include <utility>
#include <set>     
using namespace std;
typedef long long LL;
const int N = 1e6 +10; 
int arr[N];
int S[N];

typedef pair<int, int> PA;
typedef pair<PA, int> PA2;
int k,n;


int  SG(int x) {
    if(S[x]!= -1)           //记忆化搜索
        return S[x];
    set<int> status;
    for(int i = 0; i < k; i++)
    {
        int sum = arr[i];        
        if (x >= sum) 
            status.insert(SG(x - sum));
    }
    for (int i = 0; ; i++) 
        if (!status.count(i)) 
            return S[x] = i; 
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> k ;
    int res = 0;
    memset(S, -1, sizeof S);
    for(int i = 0;i < k; i++)
    {
        cin >> arr[i];
    }
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        
        res ^= SG(tmp);
    }
    if(res)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

}

AcWing 894. 拆分-Nim游戏

  • 任意一个较小堆的拆分情况会被完全包含在较大堆中（sg嵌套sg）

  • 采用递归，求出x时的sg()函数，

  • 使用全局unordered_set维护sg(x)的函数值，进行剪枝优化（第一次调用最耗时）
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
#include <cstring>
#include <iostream>
#include <utility>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 1e5 +10; 
int arr[N];

typedef pair<int, int> PA;
typedef pair<PA, int> PA2;
int n,m;
unordered_set<int> st;

int ss[N];

int sg(int x) {
    if(ss[x] != -1) return ss[x];
         
    for(int i = 0; i < x; i++)
        for(int j = 0; j<= i; j++)
    {
        st.insert(sg(i)^sg(j));
    }

    for(int i = 0; ;i++)
        if(!st.count(i))
            return ss[x] = i;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);			
    cin >> n;
    int res = 0;
    memset(ss, -1, sizeof ss);
    while(n--) {
        int tmp = 0;
        cin >> tmp;
        res ^= sg(tmp);
    }
    if(res) 
        cout << "Yes" <<endl;
    else
        cout << "No" << endl;
    
}