蓝桥杯 6.数学

蓝桥杯 6.数学

线性代数与矩阵运算&数论

矩阵乘法&整除&同余&GCD&LCM

矩阵乘法

介绍

• 线性代数中的基础内容. 只有当相乘的两个矩阵的左矩阵的列数和右矩阵的行数相同时, 才能相乘
• $n\ast m$的矩阵和$m\ast k$的矩阵做乘法后的矩阵大小为$n\ast k$

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
ll a[N][N], b[N][N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m, k; cin >> n >> m >> k;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 1; i <= m; i++){
    for(int j = 1; j <= k; j++){
      cin >> b[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= k; j++){
      ll ans = 0;
      for(int x = 1; x <= m; x++){
        ans += a[i][x] * b[x][j];
      }
      cout << ans << " ";
    }
    cout << "\n";
  }
  
  return 0;
}

整除

简介

• 在计算机中, 整数之间的除法往往是整除且向下取整
• $12/5=2$如果想要向上取整$12/5=3$, 只需要将式子改为$(a+b-1)/b$, 即$(12+5-1)/5$
• 如果x可以被y整除, 记作$y|x$, 例如$4|12$
• 整除的性质

同余

简介

• 两个或多个数字x, 对于一个模数M的余数是相等的, 或者说在模M意义下, 他们是相等的
• 例如M=7, x=[1, 8, 15, 22, 50]是同余的, 这些x都有一个共同的性质, 就是x%M=1

GCD&LCM

简介

• GCD是最大公约数, LCM是最小公倍数, 大多数情况下, 更关注GCD, 而LCM可以通过GCD求出来
• GCD通过欧几里得辗转相除法得到, 不必深究其原理, 学会使用即可
• C++已经准备好了gcd和lcm函数, 可以直接调用, 分别为: __gcd(a, b), __lcm(a, b)

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

int lcm(int a, int b){
	return a / gcd(a, b) * b;
} // 这里推荐先做除法, 再做乘法, 避免溢出

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
ll n, m;

ll gcd(int a, int b){
  
  while(b){
    int digit = a % b;
    a = b;
    b = digit;
  }
  return a;
}

void AC(){
  cin >> n >> m;
  // cout << __gcd(n, m) << "\n";
  cout << gcd(n, m) << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

扩展欧几里得

算法原理

• 扩展欧几里得不仅可以求到gcd, 而且还可以求解到不定方程$ax+by=c$的解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        // 递归出口
        x = 1, y = 0;
        return a;
    }
    // 注意这里交换了x, y的参数位置
    // 那么得到的y就已经是下一层的x了, 而y也只需要减去a/b*x即可
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a, b, m;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        // 递归出口
        x = 1, y = 0;
        return a;
    }
    // 注意这里交换了x, y的参数位置
    // 那么得到的y就已经是下一层的x了, 而y也只需要减去a/b*x即可
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll getabs(ll x) {
  return x < 0 ? -x : x;
}

void AC(){
  cin >> a >> b >> m;
  ll x, y, d = exgcd(getabs(a), getabs(m), x, y);
  if(b % d){
    cout << -1 << "\n";
  } else {
    x *= (a < 0 ? -1 : 1) * (b / d);
    x = (x % (m / d) + (m / d)) % (m / d);
    cout << x << "\n";
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// const ll N = 2e5 + 5;
ll _x, _y, m, n, l;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        // 递归出口
        x = 1, y = 0;
        return a;
    }
    // 注意这里交换了x, y的参数位置
    // 那么得到的y就已经是下一层的x了, 而y也只需要减去a/b*x即可
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll getabs(ll x) {
  return x < 0 ? -x : x;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  
  cin >> _x >> _y >> m >> n >> l;
  ll a = m - n, b = l, c = _y - _x;
  ll x, y, d = exgcd(getabs(a), getabs(b), x, y);
  if(c % d){
    cout << "impossible" << "\n";
  } else {
    x *= (a < 0 ? -1 : 1) * (c / d);
    x = (x % (b / d) + (b / d)) % (b / d);
    cout << x << "\n";
  }

  return 0;
}

编程156-158

156-157没写

// 这个题不能使用递归记忆化来写, 应该使用矩阵快速幂求解
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 5;
const ll p = 1e9 + 7;
ll n, k, a[N];

struct Matrix{
  ll val[N][N];
  Matrix(){
    memset(val, 0, sizeof val);
  }
};

Matrix mul(Matrix &a, Matrix &b){
  Matrix c;
  for(int i = 1; i <= 2; i ++){
    for(int j =  1; j <= 2; j++){
      for(int k = 1; k <= 2; k++){
        c.val[i][j] = (c.val[i][j] + a.val[i][k] * b.val[k][j]) % p;
      }
    }
  }
  return c;
}

Matrix fastPow(Matrix a, ll b){
  Matrix ret;
  for(int i = 1; i <= 2; i++){
    ret.val[i][i] = 1;
  }
  while(b){
    if(b & 1) ret = mul(ret, a);
    a = mul(a, a);
    b >>= 1;
  }
  return ret;
}

int main(){
  	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll t; cin >> t;
    while(t--){
      cin >> k;
      if(k == 1 || k == 2) cout << 1 << "\n";
      else {
        Matrix xs;
        xs.val[1][1] = 1;
        xs.val[1][2] = 1;
        xs.val[2][1] = 1;
        Matrix ans = fastPow(xs, k - 2);
        cout << (ans.val[1][1] + ans.val[1][2]) % p << "\n";
      }
    }
    
  	return 0;
}

素数朴素判定&埃氏筛法

朴素的素数判定法

简介

• 又称质数, 指的是除了1和它本身, 没有其他的因子的数字

bool isPrime(int n){
    if(n < 2) return false; // <2的一定不是质数
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0) return false; // i<=n/i等价于i*i<=n, 这样可以防止溢出(sqrt()函数速度会比较慢, 而且返回类型是浮点型)
    }
    return true;
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 5;
const ll p = 1e9 + 7;

bool isPrime(ll n){
  if(n < 2) return false; // <2的一定不是质数
  for(int i = 2; i <= n / i; i++){
    if(n % i == 0) return false; // i<=n/i等价于i*i<=n, 这样可以防止溢出(sqrt()函数速度会比较慢, 而且返回类型是浮点型)
  }
  return true;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    ll sum = 0, j = i;
    while(j){
      sum += j % 10;
      j /= 10;
    }
    if(isPrime(sum)){
      ans++;
    }
  }
  cout << ans << "\n";
  return 0;
}

埃氏筛法

简介

• 对于一个合数(即不是素数), 它必然存在一个质数的因子, 也就是说合数一定是某个较小的质数的倍数, 所以我们不妨枚举倍数
• 埃氏筛法: 已知2是一个质数, 然后将2的所有大于它本身的倍数全部"筛掉", 因为可以判断它们都不是质数, 然后到3, 4…, 如果枚举到的数字i没有被筛掉, 说明在[2~i-1]不存在某个数字可以整除i, 于是就可以直接判定i是一个质数, 然后再将i所有的倍数全部筛掉

bool vis[N]; // vis[i] = true表示被筛掉了
vis[0] = vis[1] = true;
for(int i = 2; i <= n; i++){
    if(!vis[i]){ // 没有被筛掉
        for(int j = 2 * i; j <= n; j += i){ // 枚举所有大于i的倍数, 也就是从2i开始, j+=i也就是i的倍数
            vis[j] = true; // 筛掉
        }
    }
}

例题讲解

// 暴力枚举
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll p = 1e9 + 7;
vector<ll> vec;
bool isPrime(ll n){
  if(n < 2) return false; // <2的一定不是质数
  for(int i = 2; i <= n / i; i++){
    if(n % i == 0) return false; // i<=n/i等价于i*i<=n, 这样可以防止溢出(sqrt()函数速度会比较慢, 而且返回类型是浮点型)
  }
  return true;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  
  for(int i = 1; i <= n; i++){
    if(isPrime(i)){
      vec.push_back(i);
    }
  }
  ll ans = 0;
  for(int i = 0; i < vec.size(); i++){
    for(int j = i; j < vec.size(); j++){
      if(isPrime(vec[j] - vec[i])){
        ans++;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}


// 埃氏筛法
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll p = 1e9 + 7;
vector<ll> vec;
bool vis[N]; // vis[i] = true表示被筛掉了

void init(ll n){
  vis[0] = vis[1] = true;
  for(int i = 2; i <= n; i++){
    if(!vis[i]){ // 没有被筛掉
      for(int j = 2 * i; j <= n; j += i){ // 枚举所有大于i的倍数, 也就是从2i开始, j+=i也就是i的倍数
        vis[j] = true; // 筛掉
      }
    }
  }
  for(int i = 2; i <= n; i++){
    if(!vis[i]){
      vec.push_back(i);
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  init(n);
  ll ans = 0;
  for(int i = 0; i < vec.size(); i++){
    for(int j = i; j < vec.size(); j++){
      if(!vis[vec[j] - vec[i]]){
        ans++;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

欧拉筛

原理

• 在埃氏筛法中, 枚举每个素数并将其所有的倍数筛除, 其中是存在一些冗余的, 例如数字30会被2筛除, 也会被3和5筛除. 如果可以保证每个合数只筛除一次, 那么就可以降低时间复杂度, 欧拉筛就是做了这么一件事, 让素数筛法的时间复杂度降低到了O(n)

void euler(int n){
    vector<int> primes;
    vis[0] = vis[1] = true;
    for(int i = 2; i <= n; i++){
        // 如果i没有被筛除, 说明i是质数, 存入vector中
   		if(!vis[i]) primes.push_back(i);     
        // 注意枚举条件i*primes[j]表示要被筛除的数字(一定不是质数)
        for(int j = 0; j < primes.size() && i * primes[j] <= n; i++){
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0){
                // 说明往后primes[j]已经不是i*primes[j]的最小质因子了
                break;
            }
        }
    }
}

时间复杂度分析

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
bool vis[N]; // vis[i] = true表示被筛掉了
ll prefix[N];
void euler(int n){
  vector<int> primes;
  vis[0] = vis[1] = true;
  for(int i = 2; i <= n; i++){
    // 如果i没有被筛除, 说明i是质数, 存入vector中
    if(!vis[i]) primes.push_back(i);     
    // 注意枚举条件i*primes[j]表示要被筛除的数字(一定不是质数)
    for(int j = 0; j < primes.size() && i * primes[j] <= n; j++){
      vis[i * primes[j]] = true;
      if(i % primes[j] == 0){
        // 说明往后primes[j]已经不是i*primes[j]的最小质因子了
        break;
      }
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, q; cin >> n >> q;
  euler(n);
  for(int i = 1; i <= n; i++) {
    prefix[i] = prefix[i -1] + (int)(!vis[i] && !vis[i / 2]);
  }
  for(int i = 0; i < q; i++){
    ll l, r; cin >> l >> r;
    
    cout << prefix[r] - prefix[l - 1] << "\n";
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e7 + 5;
bool vis[N]; // vis[i] = true表示被筛掉了
ll prefix[N], minp[N];
void euler(int n){
  vector<int> primes;
  vis[0] = vis[1] = true;
  for(int i = 2; i <= n; i++){
    // 如果i没有被筛除, 说明i是质数, 存入vector中
    if(!vis[i]) primes.push_back(i), minp[i] = i;     
    // 注意枚举条件i*primes[j]表示要被筛除的数字(一定不是质数)
    for(int j = 0; j < primes.size() && i * primes[j] <= n; j++){
      vis[i * primes[j]] = true;
      minp[i * primes[j]] = primes[j];
      if(i % primes[j] == 0){
        // 说明往后primes[j]已经不是i*primes[j]的最小质因子了
        break;
      }
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  euler(2e7);
  for(int i = 1; i <= 2e7; i++) {
    prefix[i] = prefix[i -1] + minp[i];
  }
  while(t--){
    ll x; cin >> x;
    cout << prefix[x] << "\n";
  }
    
  return 0;
}

编程159-161

一分为二

最小质因子之和(简单)

最小质因子之和(困难)

唯一分解定理

唯一分解定理

vector<pair<int, int>> vec;
int main(){
	int x; cin >> x;
    // 枚举所有可能的质因子
    for(int i = 2; i <= x / i; x++){
		// 如果不能整除直接跳过
        if(x % i) continue;
        
        // 如果可以整除, 那么必然是一个质因子(从小到大的特性决定)
  		// cnt表示当前这个质因子i的指数      
        int cnt = 0;
        // 一直除, 知道除干净
        while(x % i == 0) cnt ++, c /= i;
		vec.push_back({i, cnt});
    }
    if(x > 1) vec.push_back({x, 1});
    for(const auto i : vec) cout << i.first << " " << i.second << "\n";
    return 0;
}

约数个数定理

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 105;
ll a[N];

void f(int x){
  // 枚举所有可能的质因子
  for(int i = 2; i <= x / i; i++){
    // 如果不能整除直接跳过
    if(x % i) continue;
    // 一直除, 知道除干净
    while(x % i == 0) a[i] ++, x /= i;
  }
  if(x > 1) a[x]++;
  
}

int main(){
  int x = 100;
  for(int i = 1; i <= x; i++){
    f(i);
  }

  ll ans = 1;
  for(int i = 1; i <= x; i++){
    ans = ans * (a[i] + 1);
  }
  cout << ans << "\n";
  return 0;
}

约束和定理

编程162-163

没写

快速幂

简介

• 朴素的计算a的b次方的方法, 所需的时间复杂度为O(b)
• 利用倍增的思想, 可以将求幂运算的时间复杂度降低为O(logb)
• 当b为偶数: $a^b=a^{(}b/2)\ast a^{(}b/2)=(a^2{)}^{(}b/2)$
• 当b为奇数: $a^b=a\ast a^{(}b/2)\ast a^{(}b/2)=a\ast (a^2{)}^{(}b/2)$, 注意这里b/2是向下取整
• 于是迭代求解, 直到b为0即可

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a[N], n, m, p;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

void AC(){
  cin >> n >> m >> p;
  cout << qmi(n, m) << "\n";
}

int main(){
  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

费马小定理&逆元

费马小定理

逆元

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
const ll p = 1e9 + 7;
ll a[N], n;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x){
  return qmi(x, p - 2);
}

void AC(){
  cin >> n;
  cout << inv(n) << "\n";
}

int main(){
  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
const ll p = 1e9 + 7;
ll a[N], n, k;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x){
  return qmi(x, p - 2);
}

int main(){
  cin >> n >> k;
  if(k == 0){
    cout << 1 << "\n";
    for(int i = 2; i <= n; i++){
      cout << 0 << "\n";
    }
  } else if (k & 1){
    ll ans = inv(n / 2);
    for(int i = 1; i <= n; i++){
      if(i & 1) cout << 0 << "\n";
      else cout << ans << "\n";
    }
  } else {
    ll ans = inv((n + 1) / 2);
    for(int i = 1; i <= n; i++){
      if(i & 1) cout << ans << "\n";
      else cout << 0 << "\n";
    }
  }
  
  return 0;
}

编程164-166

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a[N], n, p;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x){
  return qmi(x, p - 2);
}

int main(){
  cin >> n >> p;
  cout << inv(n) << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a, b, p;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

int main(){
  cin >> a >> b >> p;
  cout << qmi(a, b) << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a, p;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x){
  return qmi(x, p - 2);
}

int main(){
  cin >> a >> p;
  if(a % p == 0){
    cout << "Inverse doesn't exist\n";
  } else {
    cout << inv(a) << "\n";
  }
  
  return 0;
}

欧拉函数&欧拉降幂

欧拉函数

ll phi = n;
for(int i = 2; i <= n; i++){
    if(n & 1) continue;
    phi = phi / i * (i - 1);
    while(n % i == 0) n /= i;
}
if(n > 1) phi = phi / n * (n - 1);

欧拉降幂

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
const ll p = 1e9 + 7;
ll n, m;

// 快速幂
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

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

  // 欧拉函数
  ll c = 1e9 + 7, phi = c;
  for(int i = 2; i <= c / i; i++){
      if(c % i) continue;
      phi = phi / i * (i - 1);
      while(c % i == 0) c /= i;
  }
  if(c > 1) phi = phi / c * (c - 1);
 
  // 求m的阶乘
  ll ans = 1;
  for(int i = 1; i <= m; i++){
    ans = ans * i % phi; // 为了防止溢出, 每次乘的时候都 % phi
  }
 
  cout << qmi(n, ans) << "\n";
  
  return 0;
}

编程167-169

167为乘积幂次那道题

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
const ll p = 1e9 + 7;
ll n;

// 欧拉函数
ll euler_phi(ll c){
  
  ll phi = c;
  for(int i = 2; i <= c / i; i++){
      if(c % i) continue;
      phi = phi / i * (i - 1);
      while(c % i == 0) c /= i;
  }
  if(c > 1) phi = phi / c * (c - 1);
  return phi;
}
int main(){
  cin >> n;
  
  cout << euler_phi(n) << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll n;

// 快速幂
ll qmi(ll a, ll b, ll p){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

// 欧拉函数
ll euler_phi(ll c){
  ll phi = c;
  for(int i = 2; i <= c / i; i++){
      if(c % i) continue;
      phi = phi / i * (i - 1);
      while(c % i == 0) c /= i;
  }
  if(c > 1) phi = phi / c * (c - 1);
  return phi;
}

int main(){
  n = 2023;

  int a = euler_phi(n);
  for(int i = 2022; i >= 3; i--){
    n = qmi(i, n, a);
  }
  n = qmi(2, n, 2023);

  cout << n << "\n";
  
  return 0;
}

裴蜀定理

简介

证明

推广

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;

int main(){
  ll t; cin >> t;
  ll a, b; 
  for(int i = 1; i <= t; i++){
    cin >> a >> b;
    if(a < 0) a = -a;
    if(b < 0) b = -b;
    cout << __gcd(a, b) << "\n";
  }

  
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;

int main(){
  ll a, b; cin >> a >> b;
  cout << a * b - a - b << "\n"; // 裴蜀定理的推广(最大的不能表示的整数)
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a[N];

bool dp[N];

int main(){
  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  ll d = a[1];
  for(int i = 2; i <= n; i++){
    d = __gcd(d, a[i]);
  }
  if(d == 1){
    int m = a[1] * a[2] - a[1] - a[2];
    dp[0] = true;
    for(int i = 1; i <= n; i++){
      for(int j = a[i]; j <= m; j++){
        dp[j] |= dp[j - a[i]];
      }
    }
    int ans = 0;
    for(int i = 0; i <= m; i++) ans += (dp[i] == false);
    cout << ans << "\n";
  } else {
    cout << "INF" << "\n";
  }
  
  
  return 0;
}

编程170-174

171-173是上面例题

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5  + 5;
ll a[N], GCD;

int main(){
  ll n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    GCD = __gcd(GCD, a[i]);
  }
  cout << m / GCD << "\n";
  
  
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5  + 5;
ll a[N], GCD;

int main(){
  ll n, x; cin >> n >> x;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    GCD = __gcd(GCD, a[i]);
  }
  cout << x % GCD << "\n";
    
  return 0;
}

组合数学

计数原理

前置基础知识

分类加法

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5  + 5;
const ll p = 1e9 + 7;

ll qmi(ll a, ll b){ // 快速幂
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x) {return qmi(x, p - 2);} // 逆元

ll Cnk(ll n, ll k){ // 排列组合, 这个地方不能使用n的阶乘, 因为会溢出
  ll res = 1;
  for(int i = n; i >= n - k + 1; i--) res = res * i % p;
  for(int i = 1; i <= k; i++) res = res * inv(i) % p;
  return res;
}

ll mo(ll x) {return (x % p + p) % p;} // 取模函数, 防止溢出和防止对分数取模

int main(){
  ll n, a, b; cin >> n >> a >> b;
   // 性质: Cn0+Cn1+Cn2+...+Cnn = 2^n, Cn0=1, 使用2^n将Cn0和Cna,Cnb减掉即可
  ll ans = mo(mo(qmi(2ll, n) - 1 - Cnk(n, a)) - Cnk(n, b));
  cout << ans << "\n";
    
  return 0;
}

分步乘法

组合数常用计算方法

DP法求组合数

预处理阶乘法求组合数

差异对比

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<ll>> C;

int main(){
  ll n, m, c; cin >> n >> m >> c;
  C.resize(n + 1);
  for(int i = 0; i <= n; i++){
    C[i].resize(m + 1);
    C[i][0] = 1;
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % c;
    }
  }
  cout << C[n][m] << "\n";
    
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const ll N = 1e7 + 5;

ll fac[N], invfac[N];

ll qmi(ll a, ll b){ // 快速幂
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

ll inv(ll x) {return qmi(x, p - 2);} // 逆元

void init(){
  int n = 1e7;
  fac[0] = 1;
  for(int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % p;
  invfac[n] = inv(fac[n]);
  for(int i = n - 1; i >= 0; i--) invfac[i] = (i + 1) * invfac[i + 1] % p;
}

ll C(ll n, ll m){ // 排列组合, 这个地方不能使用n的阶乘, 因为会溢出
  if(n < 0 || m < 0 || n < m) return 0;
  return fac[n] * invfac[n - m] % p * invfac[m] % p; 
}

int main(){
  ll q; cin >> q;
  init();
  while(q--){
    ll n, m; cin >> n >> m;
    cout << C(n, m) << "\n";
  }
  
    
  return 0;
}

排列组合专项

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1000000007;
const ll N = 1e7 + 5;

ll qmi(ll a, ll b){ // 快速幂
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}

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

  cout << (6 * qmi(2, n) + 6 * qmi(2, m) - 24 + p) % p << "\n"; // +p处理负数
  
    
  return 0;
}

二元组计数专项

#include <iostream>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], prefix[N], cnt[N]; // cnt[x]表示到当前为止, prefix对k取模后为x的元素个数(包括prefix[0])

int main() {
    ll n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = (prefix[i - 1] + a[i]) % k;
    }
    ll ans = 0;
    cnt[0] = 1;
    for (ll i = 1; i <= n; i++) {
      // 维护的是(0, i - 1)的信息
      ans += cnt[prefix[i]];
      // 加上i的信息
      cnt[prefix[i]]++;
    }
    cout << ans << "\n";


    return 0;
}

编程175-181

// 样例过了一半, 还有一半没过

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 5e5 + 5;
const ll p = 1e9 + 7;
ll jc[N], inv_jc[N];

ll mo(ll x) {return (x % p + p) % p;} // 取模函数, 防止溢出和防止对分数取模

ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p; // b为奇数, 乘一个a到答案里面
        a = a * a % p, b >>= 1; // 底数平方并对p去模, 指数除以2
    }
    return res;
}
ll inv(ll x){
  return qmi(x, p - 2);
}

ll Cnk(ll n, ll k){ // 排列组合, 这个地方不能使用n的阶乘, 因为会溢出
  ll res = 1;
  for(ll i = n; i >= n - k + 1; i--) res = res * i % p;
  for(ll i = 1; i <= k; i++) res = res * inv(i) % p;
  return res;
}

ll A(ll x, ll y){
  if(y == 0) return 1;
  else if(x == y) return jc[x];
  else if(y < 0 || y > x) return 0;
  else return jc[x] * inv_jc[x - y] % p;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    jc[0] = 1;
    for(ll i = 1; i <= N - 5; i++) {
      jc[i] = jc[i - 1] * i % p;
    }

    inv_jc[N - 5] = inv(jc[N - 5]);

    for(ll i = N - 6; i >= 1; i--){
      inv_jc[i] = inv_jc[i + 1] * (i + 1) % p;
    }
    ll n, m; cin >> n >> m;
    ll ans = 0;
    for (ll i = 0; i <= n; i++) {
      ll f = (i & 1) ? -1 : 1;
      ans = mo(ans + mo(mo(f * Cnk(n, i)) * A(m - i, n - i)));
    }
    cout << ans * A(m, n) % p << "\n";


    return 0;
}

176-181没写

178, 180上面有