• 数学知识总结

    素数

    质数/素数定义

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

    判断素数（试除法）

    约数有一个重要的性质：

    假设n代表数字，d代表n的一个约数

    即d能整除n(d|n)

    那么n/d为n的另外一个约数

    即n/d能整除d(n/d | n)

    简单思路：

    模板：

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

     866. 试除法判定质数

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. bool is_prime(int n)
    8. {
    9.     if (n <= 1) return false;
    10.     
    11.     for (int i = 2; i <= n / i; i ++ )
    12.       if (n % i == 0) return false;
    13.      
    14.     return true;
    15. }
    16. int main()
    17. {
    18.     int n;
    19.     cin >> n;
    20.     
    21.     while (n --)
    22.     {
    23.         int a;
    24.         cin >> a;
    25.         if (is_prime(a)) puts("Yes");
    26.         else puts("No");
    27.     }
    28.     
    29.     return 0;
    30. }

    分解质因数（试除法）

    从小到大枚举所有的数

    为什么不需要判断是否为质因子？

    因为i是n的因子，即n是i的倍数，当枚举的到i时，n中已经不包含有2~i-1的因子，即i中也不包含，2~i-1的因子，所以i是质数

    n中最多只包括一个大于sqrt(n)的质因子

    如果最后剩下一个大于1的数，那就是大于sqrt(n)的质因子

    模板：

    1. ​
    2. void divide(int n)
    3. {
    4.     for (int i = 2; i <= n / i; i ++ )
    5.     {
    6.         if (n % i == 0)
    7.         {
    8.             int cnt = 0;
    9.              while (n % i == 0)
    10.              {
    11.                  cnt ++;
    12.                  n /= i;
    13.              }
    14.              printf("%d %d\n", i, cnt);
    15.         }
    16.     }
    17.     if (n > 1) printf("%d %d\n", n, 1);
    18.     printf("\n");
    19. }
    20.  
    21. ​

    acwing 867. 分解质因数

    1. ​​​​​​#include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6.  
    7. void divide(int n)
    8. {
    9.     for (int i = 2; i <= n / i; i ++ )
    10.     {
    11.         if (n % i == 0)
    12.         {
    13.             int cnt = 0;
    14.              while (n % i == 0)
    15.              {
    16.                  cnt ++;
    17.                  n /= i;
    18.              }
    19.              printf("%d %d\n", i, cnt);
    20.         }
    21.     }
    22.     if (n > 1) printf("%d %d\n", n, 1);
    23.     printf("\n");
    24. }
    25.  
    26. int main()
    27. {
    28.     int n;
    29.     scanf("%d", &n);
    30.     
    31.     while (n --)
    32.     {
    33.         int a;
    34.         scanf("%d", &a);
    35.         divide(a);
    36.     }
    37.     
    38.     return 0;
    39. }

      埃氏筛法

    算法思路：

     模板：

    1. void gets_prime(int n)
    2. {
    3.     for (int i = 2; i <= n; i ++ )
    4.     {
    5.         if (!st[i])
    6.         {
    7.             cnt ++;
    8.             for (int j = i * 2; j <= n; j += i) st[j] = true;
    9.         }
    10.     }
    11. }

    868. 筛质数

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6. const int N = 1000010;
    7. bool st[N];
    8. int cnt;
    9.  
    10. void gets_prime(int n)
    11. {
    12.     for (int i = 2; i <= n; i ++ )
    13.     {
    14.         if (!st[i])
    15.         {
    16.             cnt ++;
    17.             for (int j = i * 2; j <= n; j += i) st[j] = true;
    18.         }
    19.     }
    20. }
    21. int main()
    22. {
    23.     int n;
    24.     cin >> n;
    25.     gets_prime(n);
    26.     cout << cnt << endl;
    27. }

     线性筛（欧拉筛法）

    算法思路：

    模板：

    1. void oula(int n)
    2. {
    3.     for (int i = 2; i <= n; i ++ )
    4.     {
    5.         if (!st[i]) primes[cnt ++] = i;
    6.         for (int j = 0; primes[j] <= n / i; j ++ )
    7.         {
    8.             st[i * primes[j]] = true;
    9.             if (i % primes[j] == 0) break;
    10.         }
    11.     }
    12. }

     868. 筛质数

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = 1000010;
    8. int primes[N];
    9. bool st[N];
    10. int cnt;
    11.  
    12. void oula(int n)
    13. {
    14.     for (int i = 2; i <= n; i ++ )
    15.     {
    16.         if (!st[i]) primes[cnt ++] = i;
    17.         for (int j = 0; primes[j] <= n / i; j ++ )
    18.         {
    19.             st[i * primes[j]] = true;
    20.             if (i % primes[j] == 0) break;
    21.         }
    22.     }
    23. }
    24.  
    25. int main()
    26. {
    27.     int n;
    28.     cin >> n;
    29.     oula(n);
    30.     cout << cnt << endl;
    31. }

    约数

    试除法

    思路：

    模板：

    1.  
    2. int res = 0;
    3. for (int i = 1; i <= n / i; i ++ )
    4. {
    5.     if (n % i == 0)
    6.     {
    7.         if (i == n / i) res += 2;
    8.         else res += 1;
    9.     }
    10. }

     —————————————这就是纯暴力解法，时间复杂度高——————————————

    通过算数基本定理来求约数个数

    思路：

     模板：

    1. unordered_map<int, int> prime;//prime[质因子] = 次方
    2. for (int i = 2; i <= x / i; i ++ )//分解质因数
    3. {
    4.     if (x % i == 0)
    5.     {
    6.         while (x % i == 0)
    7.         {
    8.             x /= i;
    9.             prime[i] ++;
    10.         }
    11.  
    12.     }
    13. }
    14. if (x > 1) prime[x] ++;
    15. long long res = 1;
    16. for (auto it = prime.begin(); it != prime.end(); it ++)
    17. {
    18.     res = res * (prime->second + 1);
    19. }

    870. 约数个数

    输入样例： 

    1. 3
    2. 2
    3. 6
    4. 8

    代码展示：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. typedef long long LL;
    9. const int mod = 1e9 + 7;
    10.  
    11. int main()
    12. {
    13.    int n;
    14.    scanf("%d",&n);
    15.    
    16.    unordered_map<int, int> prime;
    17.    
    18.    while (n --)
    19.    {
    20.        int x;
    21.        cin >> x;
    22.        for (int i = 2; i <= x / i; i ++ )
    23.        {
    24.             while (x % i == 0)
    25.             {
    26.                 x /= i;
    27.                 prime[i] ++;
    28.             }
    29.        }
    30.        if (x > 1) prime[x] ++;
    31.    }
    32.    
    33.    LL res = 1;
    34.    for (auto p : prime) res = res * (p.second + 1) % mod;
    35.    printf("%lld\n",res);
    36. }

    ————————————————————next—————————————————————

    通过算术基本定理求约数之和 

    思路：

    模板： 

    1. unordered_map<int, int> prime;//prime[质因子] = 次方
    2. for (int i = 2; i <= x / i; i ++ )//分解质因数
    3. {
    4.     if (x % i == 0)
    5.     {
    6.         while (x % i == 0)
    7.         {
    8.             x /= i;
    9.             prime[i] ++;
    10.         }
    11.  
    12.     }
    13. }
    14. if (x > 1) prime[x] ++;
    15. long long res = 1;
    16. for (auto it = prime.begin(); it != prime.end(); it ++)
    17. {
    18.      int a = it->first, b = it->second;
    19.      long long t = 1;
    20.      for (int i = 0; i < b; i ++) t = t * a + 1;
    21.      res = res * t;  
    22. }

    871. 约数之和

    输入样例：

    1. 3
    2. 2
    3. 6
    4. 8

     代码展示：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. typedef long long LL;
    9. const int mod = 1e9 + 7;
    10.  
    11. int main()
    12. {
    13.     int n;
    14.     scanf("%d",&n);
    15.     
    16.     unordered_map<int, int> prime;
    17.     
    18.     while (n --)
    19.     {
    20.         int x;
    21.         cin >> x;
    22.  
    23.         for (int i = 2; i <= x / i; i ++ )
    24.         {
    25.             while (x % i == 0)
    26.             {
    27.                 prime[i] ++;
    28.                 x /= i;
    29.             }
    30.         }
    31.         if (x > 1) prime[x] ++;
    32.     }
    33.     LL res = 1;
    34.     for (auto p : prime)
    35.     {
    36.         int a = p.first, b = p.second;
    37.         LL t = 1;
    38.         for (int i = 0; i < b; i ++ ) t = (t * a + 1) % mod;
    39.         res = res * t % mod;
    40.     }
    41.    cout << res << endl;
    42. }

    ———————————————————next—————————————————————

    求最大公约数 

    思路：

    模板： 

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

    输入样例：

    1. 2
    2. 3 6
    3. 4 6

     AcWing 872. 最大公约数

    代码展示：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. int gcd(int a, int b)
    8. {
    9.     return b ? gcd(b, a % b) : a;
    10. }
    11.  
    12. int main()
    13. {
    14.     int n;
    15.     cin >> n;
    16.     
    17.     while (n --)
    18.     {
    19.         int a, b;
    20.         cin >> a >> b;
    21.         int ans = gcd(a, b);
    22.         cout << ans << endl;
    23.     }
    24.     
    25.     return 0;
    26. }

    欧拉函数

    基本思路：

     

     模板（暴力）：

    1. long long res = x;
    2. for (int i = 2; i <= x / i; i ++ )
    3. {
    4.     if (x % i == 0)
    5.     {
    6.         while (x % i == 0) x /= i;
    7.         res = res * (i - 1) / i;
    8.     }
    9. }
    10. if (x > 1) res = res * (x - 1) / x;

    Acwing873. 欧拉函数

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

     模板（线性筛法）：

    1. const int N = 1e6 + 10;
    2. int primes[N], cnt;
    3. bool st[N];
    4. int phi[N];
    5.  
    6. void oula(int x)
    7. {
    8.     phi[1] = 1;
    9.     for (int i = 2; i <= x; i ++)
    10.     {
    11.         if (!st[i])
    12.         {
    13.             primes[cnt ++] = i;
    14.             phi[i] = i - 1;
    15.         }
    16.         for (int j = 0; primes[j] <= x / i; j ++)
    17.         {
    18.             st[i * primes[j]] = true;
    19.             phi[i * primes[j]] = primes[j] * phi[i] * (primes[j] - 1) / primes[j];
    20.             if (i % primes[j] == 0)
    21.             {
    22.                 phi[i * primes[j]] = primes[j] * phi[i];
    23.                 break;
    24.             } 
    25.         }
    26.     }
    27. }

    运用线性筛算欧拉函数思路：

    Acwing874. 筛法求欧拉函数

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1e6 + 10;
    7. int primes[N], cnt;
    8. bool st[N];
    9. int phi[N];
    10.  
    11. void oula(int x)
    12. {
    13.     phi[1] = 1;
    14.     for (int i = 2; i <= x; i ++)
    15.     {
    16.         if (!st[i])
    17.         {
    18.             primes[cnt ++] = i;
    19.             phi[i] = i - 1;
    20.         }
    21.         for (int j = 0; primes[j] <= x / i; j ++)
    22.         {
    23.             st[i * primes[j]] = true;
    24.             phi[i * primes[j]] = primes[j] * phi[i] * (primes[j] - 1) / primes[j];
    25.             if (i % primes[j] == 0)
    26.             {
    27.                 phi[i * primes[j]] = primes[j] * phi[i];
    28.                 break;
    29.             } 
    30.         }
    31.     }
    32. }
    33. int main()
    34. {
    35.     int n;
    36.     cin >> n;
    37.    
    38.     oula(n);
    39.     long long res = 0;
    40.     for (int i = 1; i <= n; i ++) res += phi[i];
    41.     cout << res << endl;
    42.    
    43. }

    快速幂

    基本思路：

    模板：

    1. typedef long long LL;
    2.  
    3. LL qmi(int a, int k, int p)
    4. {
    5.     LL res = 1;
    6.     while (k)
    7.     {
    8.         if (k & 1) res = res * a % p;
    9.         k >>= 1;
    10.         a = (LL)a * a % p;
    11.     }
    12.     return res;
    13. }

     AcWing 875. 快速幂

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. typedef long long LL;
    8.  
    9. LL qmi(int a, int k, int p)
    10. {
    11.     LL res = 1;
    12.     while (k)
    13.     {
    14.         if (k & 1) res = res * a % p;
    15.         k >>= 1;
    16.         a = (LL)a * a % p;
    17.     }
    18.     return res;
    19. }
    20. int main()
    21. {
    22.     int n;
    23.     cin >> n;
    24.     
    25.     while (n --)
    26.     {
    27.         int a, k, p;
    28.         cin >> a >> k >> p;
    29.         cout << qmi(a, k, p) << endl;
    30.     }
    31. }

     快速幂求逆元思路：

     AcWing 876. 快速幂求逆元  

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7.  
    8. LL qmi(int a, int k, int p)
    9. {
    10.     LL res = 1;
    11.     while (k)
    12.     {
    13.         if (k & 1) res = res * a % p;
    14.         k >>= 1;
    15.         a = (LL) a * a % p;
    16.     }
    17.     return res;
    18. }
    19. int main()
    20. {
    21.     int n;
    22.     cin >> n;
    23.     
    24.     while (n --)
    25.     {
    26.         int a, p;
    27.         cin >> a >> p;
    28.         if (a % p) cout << qmi(a, p - 2, p) << endl;
    29.         else puts("impossible");
    30.     }
    31. }

    扩展欧几里得

    基本思路：

    模板：

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

     Acwing877. 扩展欧几里得算法

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int exgcd(int a, int b, int &x, int &y)
    7. {
    8.     if (b == 0)
    9.     {
    10.         x = 1, y = 0;
    11.         return a;
    12.     }
    13.     int d = exgcd(b, a % b, y, x);
    14.     y = y - a / b * x;
    15.     return d;
    16. }
    17. int main()
    18. {
    19.     int n;
    20.     cin >> n;
    21.     while (n --)
    22.     {
    23.         int a, b, x, y;
    24.         cin >> a >> b;
    25.         exgcd(a, b, x, y);
    26.         cout << x << ' ' << y << endl;
    27.     }
    28. }

     裴蜀定理：

    对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

     Acwing878. 线性同余方程

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7. int exgcd(int a, int b, int &x, int &y)
    8. {
    9.     if (b == 0)
    10.     {
    11.         x = 1, y = 0;
    12.         return a;
    13.     }
    14.     int d = exgcd(b, a % b, y, x);
    15.     y = y - a / b * x;
    16.     return d;
    17. }
    18. int main()
    19. {
    20.     int n;
    21.     cin >> n;
    22.     while (n --)
    23.     {
    24.         int a, b, m, x, y;
    25.         cin >> a >> b >> m;
    26.         int d = exgcd(a, m, x, y);
    27.         if (b % d) puts("impossible");
    28.         else cout << (LL)x * (b / d) % m << endl;
    29.     }
    30. }

    中国剩余定理

    定义（来自百度百科）：

    AcWing 204. 表达整数的奇怪方式

    基本思路：

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7. LL exgcd(LL a, LL b, LL &x, LL &y)
    8. {
    9.     if (b == 0)
    10.     {
    11.         x = 1, y = 0;
    12.         return a;
    13.     }
    14.     LL d = exgcd(b, a % b, y, x);
    15.     y -= a / b * x;
    16.     return d;
    17. }
    18. int main()
    19. {
    20.     int n;
    21.     cin >> n;
    22.     
    23.     LL a1, m1, x;
    24.     cin >> a1 >> m1;
    25.     
    26.     for (int i = 0; i < n - 1; i ++ )
    27.     {
    28.         LL a2, m2;
    29.         cin >> a2 >> m2;
    30.         LL k1, k2;
    31.         LL d = exgcd(a1, a2, k1, k2);
    32.         if ((m2 - m1) % d)
    33.         {
    34.             x = -1;
    35.             break;
    36.         }
    37.         k1 = k1 * ((m2 - m1) / d);
    38.         
    39.         LL t = a2 / d;
    40.         
    41.         k1 = (k1 % t + t) % t;
    42.        
    43.         x = k1 * a1 + m1;
    44.         
    45.         m1 = k1 * a1 + m1;
    46.         a1 = abs(a1 / d * a2);
    47.     }
    48.     if (x != -1) x = (m1 % a1 + a1) % a1;
    49.     cout << x << endl;
    50. }

    求组合数

    方法：

    1. 递推

    动态规划思想：

    AcWing 885. 求组合数 I 

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 2010, mod = 1e9 + 7;
    7. int C[N][N];
    8.  
    9. void dp()
    10. {
    11.     for (int i = 0; i < N; i ++ )
    12.     {
    13.         for (int j = 0; j <= i; j ++ )
    14.         {
    15.             if (!j) C[i][j] = 1; //从i件物品中选取0件的方案数为1
    16.             else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; //状态转移方程
    17.         }
    18.     }
    19. }
    20. int main()
    21. {
    22.     int n;
    23.     cin >> n;
    24.     
    25.     dp();
    26.     while (n --)
    27.     {
    28.         int a, b;
    29.         cin >> a >> b;
    30.         cout << C[a][b] << endl;
    31.     }
    32.     
    33.     return 0;
    34. }

    2.预处理

    思路：

    模板： 

    1. //快速幂
    2. int qmi(int a, int k, int p)
    3. {
    4.     int res = 1;
    5.     while (k)
    6.     {
    7.         if (k & 1) res = (LL)res * a % p;
    8.         a = (LL)a * a % p;
    9.         k >>= 1;
    10.     }
    11.     return res;
    12. }
    13. //预处理
    14. void initial()
    15. {
    16.     fact[0] = 1;
    17.     infact[0] = 1;
    18.     for (int i = 1; i < N; i ++)
    19.     {
    20.         fact[i] = (LL)fact[i - 1] * i % mod;
    21.         infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    22.     }
    23. }

    AcWing 886. 求组合数 II 

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7. const int N = 1e5 + 10, mod = 1e9 + 7;
    8. int fact[N], infact[N];
    9.  
    10. //快速幂
    11. int qmi(int a, int k, int p)
    12. {
    13.     int res = 1;
    14.     while (k)
    15.     {
    16.         if (k & 1) res = (LL)res * a % p;
    17.         a = (LL)a * a % p;
    18.         k >>= 1;
    19.     }
    20.     return res;
    21. }
    22. //预处理
    23. void initial()
    24. {
    25.     fact[0] = 1;
    26.     infact[0] = 1;
    27.     for (int i = 1; i < N; i ++)
    28.     {
    29.         fact[i] = (LL)fact[i - 1] * i % mod;
    30.         infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    31.     }
    32. }
    33. int main()
    34. {
    35.     int n;
    36.     cin >> n;
    37.     
    38.     initial();
    39.     while (n --)
    40.     {
    41.         int a, b;
    42.         cin >> a >> b;
    43.         int res = (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
    44.         cout << res << endl;
    45.     }
    46. }

    3.卢卡斯（lucas）

    定义：

                    Lucas定理是用来求 c(n,m) mod p，p为素数的值。

    公式：

                    C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

    AcWing 887. 求组合数 III

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7.  
    8. //快速幂
    9. int qmi(int a, int k, int p)
    10. {
    11.     int res = 1;
    12.     while (k)
    13.     {
    14.         if (k & 1) res = (LL)res * a % p;
    15.         a = (LL)a * a % p;
    16.         k >>= 1;
    17.     }
    18.     return res;
    19. }
    20. //求组合数
    21. int C(int a, int b, int p)
    22. {
    23.     if (b > a) return 0;
    24.     int res = 1;
    25.     for (int i = 1, j = a; i <= b; i ++, j --)
    26.     {
    27.         res = (LL) res * j % p;
    28.         res = (LL) res * qmi(i, p - 2, p) % p;
    29.     }
    30.     return res;
    31.     
    32. }
    33. //卢卡斯定理
    34. int lucas(LL a, LL b, int p)
    35. {
    36.     if (a < p && b < p) return C(a, b, p);
    37.     return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
    38. }
    39. int main()
    40. {
    41.     int n;
    42.     cin >> n;
    43.     while (n --)
    44.     {
    45.         LL a, b;
    46.         int p;
    47.         cin >> a >> b >> p;
    48.         
    49.         cout << lucas(a, b, p) << endl;
    50.     }
    51. }

    4.高精度

    思路：

    Acwing888. 求组合数 IV

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = 5010;
    8. int primes[N], cnt;
    9. bool st[N];
    10. int sum[N];
    11.  
    12. //线性筛(欧拉筛)
    13. void get_primes(int n)
    14. {
    15.     for (int i = 2; i <= n; i ++)
    16.     {
    17.         if (!st[i]) primes[cnt ++] = i;
    18.         for (int j = 0; primes[j] <= n / i; j ++)
    19.         {
    20.             st[i * primes[j]] = true;
    21.             if (i % primes[j] == 0) break;
    22.         }
    23.     }
    24. }
    25. //求n中p的个数
    26. int get(int n, int p)
    27. {
    28.     int res = 0;
    29.     while (n)
    30.     {
    31.         res += n / p;
    32.         n /= p;
    33.     }
    34.     return res;
    35. }
    36. //高精度乘法
    37. vector<int> mul(vector<int> a, int b)
    38. {
    39.     vector<int> c;
    40.     int t = 0;
    41.     for (int i = 0; i < a.size(); i ++)
    42.     {
    43.         t += a[i] * b;
    44.         c.push_back(t % 10);
    45.         t /= 10;
    46.     }
    47.     while (t)
    48.     {
    49.         c.push_back(t % 10);
    50.         t /= 10;
    51.     }
    52.     return c;
    53. }
    54. int main()
    55. {
    56.     int a, b;
    57.     cin >> a >> b;
    58.     get_primes(a);
    59.     
    60.     for (int i = 0; i < cnt; i ++)
    61.     {
    62.         int p = primes[i];
    63.         sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    64.     }
    65.     
    66.     vector<int> res;
    67.     res.push_back(1);
    68.     for (int i = 0; i < cnt; i ++)
    69.         for (int j = 0; j < sum[i]; j ++)
    70.             res = mul(res, primes[i]);
    71.             
    72.     for (int i = res.size() - 1; i >= 0; i --) cout << res[i];
    73.     cout << endl;
    74.     return 0;
    75. }

    容斥原理

    基本思路：

     AcWing 890. 能被整除的数

    思路分析： 

    1.用二进制表示每种选法：1表示选当前集合，0表示不选当前集合

    2.|Sp|集合p表示1~n中p的倍数的个数，通过观察发现，|Sp| = [n | p]

    4.通过当前选中集合个数确定每一项前面的符号，再由容斥原理可以求出最终答案

     样例模拟：

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. typedef long long LL;
    7. const int N = 20;
    8. int primes[N];
    9.  
    10. int main()
    11. {
    12.     int n, m;
    13.     cin >> n >> m;
    14.     
    15.     for (int i = 0; i < m; i ++ ) cin >> primes[i];
    16.     
    17.     int res = 0;
    18.     for (int i = 1; i < 1 << m; i ++)
    19.     {
    20.         int cnt = 0; // 记录当前集合的个数,奇数个为正,偶数个为负
    21.         int t = 1; //当前选法的所有数相乘
    22.         
    23.         for (int j = 0; j < m; j ++ ) // 枚举每一位数, 为1则选该质数
    24.         {
    25.             if (i >> j & 1) //为1
    26.             {
    27.                 if ((LL)t * primes[j] > n)
    28.                 {
    29.                     t = -1;
    30.                     break;
    31.                 }
    32.                 t *= primes[j]; //当前选法质数相乘
    33.                 cnt ++; //当前选法的质数个数
    34.             }
    35.           
    36.         }  
    37.         if (t != -1)
    38.         {
    39.             if (cnt % 2) res += n / t; //奇数
    40.             else res -= n / t; //偶数
    41.         }
    42.     }
    43.     
    44.     cout << res << endl;
    45.     
    46.     return 0;
    47. }

    博弈论

    Nim游戏

    公平组合游戏ICG

    （来自算法进阶指南的摘抄）
        若一个游戏满足：
        1. 由两名玩家交替行动；
        2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
        3. 不能行动的玩家判负；
        则称该游戏为一个公平组合游戏。
        NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

    先手必胜状态

            可以走到某个必败状态 

    先手必败状态

            走不到任何一个必败状态

    基本思路及结论：

    关于位运算中异或的相关知识参考：基础算法总结_人生导师yxc的博客-CSDN博客

    证明：

    AcWing 891. Nim游戏

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8.     int n;
    9.     cin >> n;
    10.     
    11.     int res = 0;
    12.     
    13.     while (n --)
    14.     {
    15.         int x;
    16.         cin >> x;
    17.         res ^= x;
    18.     }
    19.     if (res) puts("Yes");
    20.     else puts("No");
    21.     
    22.     return 0;
    23. }

    SG函数

    mex运算：

    设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
            mex(S) = min{x}, x属于自然数，且x不属于S

    定义：

    （来自算法进阶指南）

    在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, ..., yk，定义SG(x)为x的后继节点y1, y2, ..., yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
            SG(x) = mex(SG(y1), SG(y2), ..., SG(yk))
        特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

    AcWing 893. 集合-Nim游戏

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. const int N = 10010;
    9. int s[N], f[N];
    10. int k, n;
    11.  
    12. int sg(int x)
    13. {
    14.     if (f[x] != -1) return f[x];
    15.     
    16.     unordered_set<int> S;
    17.     
    18.     for (int i = 0; i < k; i ++)
    19.     {
    20.         int sum = s[i];
    21.         if (x >= sum) S.insert(sg(x - sum));
    22.     }
    23.     
    24.     for (int i = 0; ; i ++)
    25.     {
    26.         if (!S.count(i))
    27.         {
    28.             f[x] = i;
    29.             return f[x];
    30.         }
    31.     }
    32. }
    33. int main()
    34. {
    35.     cin >> k;
    36.     for (int i = 0; i < k; i ++) cin >> s[i];
    37.     
    38.     memset(f, -1, sizeof f);
    39.     cin >> n;
    40.     
    41.     int res = 0;
    42.     for (int i = 0; i < n; i ++)
    43.     {
    44.         int x;
    45.         cin >> x;
    46.         res ^= sg(x);
    47.     }
    48.     
    49.     if (res) puts("Yes");
    50.     else puts("No");
    51.     
    52. }

     

  • 相关阅读:
    八、【Vue-Router】编程式路由导航
    代谢组学以冬虫夏草多糖的益生机制为例研究和发现关键肠道菌群
    云原生之旅 - 13）基于 Github Action 的自动化流水线
    【SpringBoot】实现引入登录时的验证码功能
    第二十七讲.动态设置相关参数(replication为2和blocksize为10字节)
    led灯珠型号及使用参数
    Linux分区指南
    MAUI+MASA Blazor 兼容性测试报告及分析
    cubeIDE开发， stm32的ADC(模数转换器) 开发要点
    SHELL中的循环语句
  • 原文地址：https://blog.csdn.net/m0_73569492/article/details/133841389