Post

数学知识

Posted Updated
By skye-ye

views 37 min read
数学知识

质数

质数的判定：试除法

时间复杂度O(sqrt(n))

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式

第一行包含整数 n。

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

输出格式

共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤100, 1≤ai≤231−1

输入样例：

1
2
3

2
2
6

输出样例：

1
2

Yes
No

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

#include <iostream>
using namespace std;

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;
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    if (is_prime(x)) puts("Yes");
    else puts("No");
  }
  
  return 0;
}

分解质因数：试除法

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

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

输出格式

对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤100, 2≤ai≤2×109

输入样例：

1
2
3

2
6
8

输出样例：

1
2
3
4

2 1
3 1

2 3

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;

void divide(int n) {
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      int s = 0;
      while (n % i == 0) {
        n /= i;
        s++;
      }
      printf("%d %d\n", i, s);
    }
  }
  if (n > 1) printf("%d %d\n", n, 1);
  puts("");
}

int main() {
  int n;
  scanf("%d", &n);
  while(n--) {
    int x;
    scanf("%d", &x);
    divide(x);
  }
}

质数筛

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤106

输入样例：

1

8

输出样例：

1

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
25
26
27

#include <iostream>
using namespace std;
const int N = 1000010;

int primes[N], cnt;
bool st[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; // primes[j]一定是i的最小质因子
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  
  get_primes(n);
  
  cout << cnt << endl;
  
  return 0;
}

约数

试除法求约数

给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行包含整数 n。

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

输出格式

输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。

数据范围

1≤n≤100, 1≤ai≤2×109

输入样例：

1
2
3

2
6
8

输出样例：

1
2

1 2 3 6 
1 2 4 8 

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

vector<int> get_divisor(int n) {
  vector<int> res;
  
  for (int i = 1; i <= n / i; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  } 
  
  sort(res.begin(), res.end());
  
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    auto res = get_divisor(x);
    for (auto t : res) cout << t << ' ';
    cout << endl;
  }
  return 0;
}

约数个数

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。

输入格式

第一行包含整数 n。

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

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。

数据范围

1≤n≤100, 1≤ai≤2×109

输入样例：

1
2
3
4

3
2
6
8

输出样例：

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

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL; 
const int mod = 1e9 + 7;

int main(){
  int n, x;
  LL ans = 1;
  unordered_map<int,int> primes;
  cin >> n;
  while(n--){
    cin >> x;
    for(int i = 2; i <= x / i; ++i){
      while(x % i == 0){
        x /= i;
        primes[i]++;
      }
    }
    if(x > 1) primes[x]++;
  }
  for(auto i : primes) ans = ans * (i.second + 1) % mod;
  cout << ans << endl;
  return 0;
}

约数之和

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。

输入格式

第一行包含整数 n。

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

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。

数据范围

1≤n≤100, 1≤ai≤2×109

输入样例：

1
2
3
4

3
2
6
8

输出样例：

1

252

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

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL; 
const int mod = 1e9 + 7;

int main(){
  int n, x;
  LL ans = 1;
  unordered_map<int,int> primes;
  cin >> n;
  while(n--){
    cin >> x;
    for(int i = 2; i <= x / i; ++i){
      while(x % i == 0){
        x /= i;
        primes[i]++;
      }
    }
    if(x > 1) primes[x]++;
  }
  for(auto i : primes) {
    int p = i.first, a = i.second;
    LL t = 1;
    while(a--) t = (t * p + 1) % mod;
    ans = ans * t % mod;
  }
  
  cout << ans << endl;
  
  return 0;
}

最大公约数：欧几里得算法/辗转相除法

给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数对 ai,bi。

输出格式

输出共 n 行，每行输出一个整数对的最大公约数。

数据范围

1≤n≤105, 1≤ai,bi≤2×109

输入样例：

1
2
3

2
3 6
4 6

输出样例：

1
2

3
2

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

#include <iostream>
using namespace std;

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

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", gcd(a, b));
  }
  return 0;
}

欧拉函数

公式法求欧拉函数

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

欧拉函数的定义

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。 若在算数基本定理中，N=pa11pa22…pamm，则： ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100, 1≤ai≤2×109

输入样例：

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

int main() {
  int n;
  cin >> n;
  while (n--) {
    int a;
    cin >> a;
    int res = a;
    
    for (int i = 2; i <= a / i; i++) 
      if (a % i == 0) {
        res = res / i * (i - 1);
        while (a % i == 0) a /= i;
      }
    if (a > 1) res = res / a * (a - 1);
    
    cout << res << endl;
  }
  
  return 0;
}

筛法求欧拉函数

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

输入格式

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

输出格式

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

数据范围

1≤n≤106

输入样例：

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
36
37
38
39

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;

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

LL get_eulers(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) {
      primes[cnt++] = i;
      phi[i] = i - 1; // 质数对应的欧拉函数值为数值减1
    }
    for (int j = 0; primes[j] <= n / i; j++) {
      st[primes[j] * i] = true;
      if (i % primes[j] == 0) {
        phi[primes[j] * i] = primes[j] * phi[i]; // 数学推导
        break;
      }
      phi[primes[j] * i] = phi[i] * (primes[j] - 1); // 数学推导
    }
  }
  
  LL res = 0;
  for (int i = 1; i <= n; i++) res += phi[i];
  
  return res;
}
int main() {
  int n;
  cin >> n;
  
  cout << get_eulers(n) << endl;
  
  return 0;
}

欧拉函数应用：欧拉定理

若a与n互质，则\(a^{\phi(n)} \equiv 1\ (mod\ n)\)

若n为质数，则可以写为\(a^{n-1} \equiv 1\ (mod\ n)\)，这便是费马定理

快速幂

快速幂算法

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

输入格式

第一行包含整数 n。

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

输出格式

对于每组数据，输出一个结果，表示 abiimodpi 的值。

每个结果占一行。

数据范围

1≤n≤100000, 1≤ai,bi,pi≤2×109

输入样例：

1
2
3

2
3 2 5
4 3 9

输出样例：

1
2

4
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

#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;
    k >>= 1;
    a = (LL) a * a % p;
  }
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, k, p;
    scanf("%d%d%d", &a, &k, &p);
    
    printf("%d\n", qmi(a, k, p));
  }
  
  return 0;
}

快速幂求逆元

运用费马定理

给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 0∼p−1 之间的逆元。

乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 ba，则存在一个整数 x，使得 ab≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(modm)。

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。

输出格式

输出共 n 行，每组数据输出一个结果，每个结果占一行。

若 ai 模 pi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围

1≤n≤105, 1≤ai,pi≤2∗109

输入样例：

1
2
3
4

3
4 3
8 5
6 3

输出样例：

1
2
3

1
2
impossible

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

#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;
    k >>= 1;
    a = (LL) a * a % p;
  }
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, p;
    scanf("%d%d", &a, &p);
    
    int res = qmi(a, p - 2, p);
    if (a % p) printf("%d\n", res);
    else puts("impossible");
  }
  
  return 0;
}

拓展欧几里得算法（裴蜀定理）

裴蜀定理

对于任意正整数 $a, b$，一定存在非零整数 $x, y$ 使得：

$ax+by=(a,b)$

求解方法：拓展欧几里得算法

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 ai,bi。

输出格式

输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的 xi,yi 均可。

数据范围

1≤n≤105, 1≤ai,bi≤2×109

输入样例：

1
2
3

2
4 6
8 18

输出样例：

1
2

-1 1
-2 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

#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;
  scanf("%d", &n);
  while (n--) {
    int a, b, x, y;
    scanf("%d%d", &a, &b);
    
    exgcd(a, b, x, y);
    
    printf("%d %d\n", x, y);
  }
}

线性同余方程

给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi)，如果无解则输出 impossible。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一组数据 ai,bi,mi。

输出格式

输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围

1≤n≤105, 1≤ai,bi,mi≤2×109

输入样例：

1
2
3

2
2 3 6
4 3 5

输出样例：

1
2

impossible
-3

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;
typedef long long LL;

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;
  scanf("%d", &n);
  while (n--) {
    int a, b, m, x, y;
    scanf("%d%d%d", &a, &b, &m);
    
    int d = exgcd(a, m, x, y);
    if (b % d) puts("impossible");
    else printf("%d\n", (LL) x * (b / d) % m);
  }
}

高斯消元

输入一个包含 n 个方程 n 个未知数的线性方程组。

方程组中的系数为实数。

求解这个方程组。

下图为一个包含 m 个方程 n 个未知数的线性方程组示例：

9a504fc2d5628535be9dcb5f90ef76c6a7ef634a.gif

输入格式

第一行包含整数 n。

接下来 n 行，每行包含 n+1 个实数，表示一个方程的 n 个系数以及等号右侧的常数。

输出格式

如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解，结果保留两位小数。

注意：本题有 SPJ，当输出结果为 0.00 时，输出 -0.00 也会判对。在数学中，一般没有正零或负零的概念，所以严格来说应当输出 0.00，但是考虑到本题作为一道模板题，考察点并不在于此，在此处卡住大多同学的代码没有太大意义，故增加 SPJ，对输出 -0.00 的代码也予以判对。

如果给定线性方程组存在无数解，则输出 Infinite group solutions。

如果给定线性方程组无解，则输出 No solution。

数据范围

1≤n≤100, 所有输入系数以及常数均保留两位小数，绝对值均不超过 100。

输入样例：

1
2
3
4

3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00

输出样例：

1
2
3

1.00
-2.00
3.00

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

#include <iostream>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-6; // 应对浮点数精度问题

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 2; // 无解
    return 1; // 有无穷多组解
  }
  
  /* 最后一行往上逆推答案 */
  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 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 == 0) {
    for (int i = 0; i < n; i++) printf("%.2lf\n", a[i][n]);
  } else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
  
  return 0;
}

求组合数

组合数1

1 <= b <= a <= 2000 递推

给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式

共 n 行，每行输出一个询问的解。

数据范围

1≤n≤10000, 1≤b≤a≤2000

输入样例：

1
2
3
4

3
3 1
5 3
2 2

输出样例：

1
2
3

3
10
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

#include <iostream>
using namespace std;
const int N = 2010, mod = 1e9 + 7;

int c[N][N];

void init() {
  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;
}

int main() {
  init();
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", c[a][b]);
  }
  return 0;
}

组合数2

1 <= b <= a <= 100000 预处理阶乘

给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式

共 n 行，每行输出一个询问的解。

数据范围

1≤n≤10000, 1≤b≤a≤105

输入样例：

1
2
3
4

3
3 1
5 3
2 2

输出样例：

1
2
3

3
10
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

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;

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() {
  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;
  }
  
  int n;
  scanf("%d", &n);
  while (n--) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", (LL) fact[a] * infact[b] % mod * infact[a - b] % mod);
  }
  return 0;
}

组合数3

1 <= b <= a <= 1018, 1 <= p <= 10000, Lucas定理：

$C_{a}^{b}\equiv C_{a\bmod p}^{b \bmod p} \times C_{a/p}^{b/p}\pmod p$

给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 Cbamodp 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一组 a,b,p。

输出格式

共 n 行，每行输出一个询问的解。

数据范围

1≤n≤20, 1≤b≤a≤1018, 1≤p≤105,

输入样例：

1
2
3
4

3
5 3 7
3 1 5
6 4 13

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>
using namespace std;
typedef long long LL;

int p;

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

int C(int a, int b) {
  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;
  }
  return res;
}

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

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

组合数4

不能模大质数，需要运用高精度计算。

  • 分解质因数
  • 高精度乘法

输入 a,b，求 Cba 的值。

注意结果可能很大，需要使用高精度计算。

输入格式

共一行，包含两个整数 a 和 b。

输出格式

共一行，输出 Cba 的值。

数据范围

1≤b≤a≤5000

输入样例：

1

5 3

输出样例：

1

10

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

#include <iostream>
#include <vector>
using namespace std;
const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[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 n, int p) {
  int res = 0;
  while (n) {
    res += n / p;
    n /= 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> res;
  res.push_back(1);
  
  for (int i = 0; i < cnt; i++)
    for (int j = 0; j < sum[i]; j++) 
      res = mul(res, primes[i]);
  
  for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
  puts("");
  
  return 0;
}

卡特兰数

转化为二维平面的路径

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

输出的答案对 109+7 取模。

输入格式

共一行，包含整数 n。

输出格式

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

数据范围

1≤n≤105

输入样例：

1

3

输出样例：

1

5

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

#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 = a; i > a - b; i--) res = (LL) res * i % mod;
  for (int i = 1; i <= b; i++) res = (LL) res * qmi(i, mod - 2, mod) % mod;
  
  res = (LL) res * qmi(n + 1, mod - 2, mod) % mod;
  
  cour << res << endl;
  
  return 0;
}

容斥原理

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数 n 和 m。

第二行包含 m 个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤16, 1≤n,pi≤109

输入样例：

1
2

10 2
2 3

输出样例：

1

7

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

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 20;

int n, m;
int p[N];

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) cin >> p[i];
  
  int res = 0;
  for (int i = 1; i < 1 << m; i++) { // 将选不选集合对应到二进制的0和1
    int t = 1, cnt = 0;
    for (int j = 0; j < m; j++)
      if (i >> j & 1) {
        cnt++;
        if ((LL) t * p[j] > n) {
          t = -1;
          break;
        }
        t *= p[j];
      }
    if (t != -1) {
      if (cnt % 2) res += n / t;
      else res -= n / t;
    }
  }
  cout << res << endl;
  
  return 0;
}

博弈论

NIM游戏

先手必胜状态：可以走到某一个必败状态

先手必败状态：走不到任何一个必败状态

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数 n。

第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n≤105, 1≤每堆石子数≤109

输入样例：

1
2

2
2 3

输出样例：

1

Yes

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

#include <iostream>
using namespace std;

int main() {
  int n;
  int res = 0;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    res ^= x;
  }
  if (res) puts("Yes");
  else puts("No");
  return 0;
}

SG函数和mex函数

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数 k，表示数字集合 S 中数字的个数。

第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。

第三行包含整数 n。

第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n,k≤100, 1≤si,hi≤10000

输入样例：

1
2
3
4

2
2 5
3
2 4 7

输出样例：

1

Yes

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 <cstring>
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 110, M = 10010;

int n, m;
int s[N], f[M];
      
int sg(int x) {
  if (f[x] != -1) return f[x];
  
  unordered_set<int> S;
  for (int i = 0; i < m; i++) {
    int sum = s[i];
    if (x >= sum) S.insert(sg(x - sum));
  }
  
  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);
  
  int res = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    res ^= sg(x);
  }
  
  if (res) puts("Yes");
  else puts("No");
  
  return 0;
}
Blogging, Algorithm
数学
This post is licensed under CC BY 4.0 by the author.