【第四讲】数学知识（2）-阿里云开发者社区

4.4 快速幂

快速幂 —— 模板题 AcWing 875. 快速幂

求 m^k mod p，时间复杂度 O(logk)。

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

4.4.1 875. 快速幂

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

输入格式

第一行包含整数 n。

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

输出格式

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

每个结果占一行。

数据范围

1≤n≤100000,

1≤ai,bi,pi≤2×109

输入样例：

3 2 5

4 3 9

输出样例：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
    LL 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;
}

4.4.2 876. 快速幂求逆元

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

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

乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡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

输入样例：

4 3

8 5

6 3

输出样例：

Impossible

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
    LL 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;
        LL res=qmi(a,p-2,p);
        if(a%p) cout<<res<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}

4.5 扩展欧几里得算法

扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法

// 求x, y，使得ax + by = gcd(a, b)
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;
}

4.5.1 877. 扩展欧几里得算法

给定 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

输入样例：

4 6

8 18

输出样例：

-1 1

-2 1

#include<bits/stdc++.h>
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,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

4.5.2 878. 线性同余方程

给定 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

输入样例：

2 3 6

4 3 5

输出样例：

impossible

-3

#include<bits/stdc++.h>
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;
    cin>>n;
    while(n--)
    {
        int a,b,m,x,y;
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if(b%d) cout<<"impossible"<<endl;
        else cout<<(LL)x*(b/d)%m<<endl;
    }
    return 0;
}

4.6 中国剩余定理

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

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。

输入格式

第 1 行包含整数 n。

第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。

输出格式

输出最小非负整数 x，如果 x 不存在，则输出 −1。

如果存在 x，则数据保证 x 一定在 64 位整数范围内。

数据范围

1≤ai≤231−1,

0≤mi<ai

1≤n≤25

输入样例：

8 7

11 9

输出样例：

#include<bits/stdc++.h>
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;
    }
    LL d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    int n;
    cin>>n;
    bool flag=true;
    LL a1,m1;
    cin>>a1>>m1;
    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)
        {
            flag=false;
            break;
        }
        k1*=(m2-m1)/d;
        LL t=a2/d;
        k1=(k1%t+t)%t;
        m1=a1*k1+m1;
        a1=abs(a1/d*a2);
    }
    if(flag) cout<<(m1%a1+a1)%a1<<endl;
    else cout<<-1<<endl;
    return 0;
}

4.7 高斯消元

高斯消元 —— 模板题 AcWing 883. 高斯消元解线性方程组

// 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];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            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; // 有唯一解
}

4.7.1 883. 高斯消元解线性方程组

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

方程组中的系数为实数。

求解这个方程组。

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

输入格式

第一行包含整数 n。

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

输出格式

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

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

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

数据范围

1≤n≤100,

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

输入样例：

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.00

-2.00

3.00

#include<bits/stdc++.h>
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+1;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[j][n]*a[i][j];
    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("%.2f\n",a[i][n]);
    }
    else if(t==1)
        cout<<"Infinite group solutions"<<endl;
    else cout<<"No solution"<<endl;
    return 0;
}

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

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

方程组中的系数和常数为 0 或 1，每个未知数的取值也为 0 或 1。

求解这个方程组。

异或线性方程组示例如下：

M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]

M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]

…

M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]

其中 ^ 表示异或(XOR)，M[i][j] 表示第 i 个式子中 x[j] 的系数，B[i] 是第 i 个方程右端的常数，取值均为 0 或 1。

输入格式

第一行包含整数 n。

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

输出格式

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

如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。

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

数据范围

1≤n≤100

输入样例：

1 1 0 1

0 1 1 0

1 0 0 1

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int a[N][N];
int gauss()
{
    int r,c;
    for(c=0,r=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[t][i],a[r][i]);
        for(int i=r+1;i<n;i++)
            if(a[i][c])
                for(int j=c;j<=n;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;j++)
            a[i][n]^=a[j][n]&a[i][j];
    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++)
            cout<<a[i][n]<<endl;
    }
    else if(t==1)
        cout<<"Multiple sets of solutions"<<endl;
    else cout<<"No solution"<<endl;
    return 0;
}

4.8 求组合数

递归法求组合数 —— 模板题 AcWing 885. 求组合数 I

// c[a][b] 表示从a个苹果中选b个的方案数
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;

通过预处理逆元的方式求组合数 —— 模板题 AcWing 886. 求组合数 II

首先预处理出所有阶乘取模的余数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;
}
// 预处理阶乘的余数和阶乘逆元的余数
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;
}

Lucas定理 —— 模板题 AcWing 887. 求组合数 III

若p是质数，则对于任意整数 1 <= m <= n，有：

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

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    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)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;
    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }
    return x * (LL)qmi(y, p - 2, p) % p;
}
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;
}

分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：

1. 筛法求出范围内的所有质数

2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + …

3. 用高精度乘法将所有质因子相乘

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)       // 求n！中的次数
{
    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;
}
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]);

卡特兰数 —— 模板题 AcWing 889. 满足条件的01序列

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)

4.8.1 885. 求组合数 I

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤10000,

1≤b≤a≤2000

输入样例：

3 1

5 3

2 2

输出样例：

#include<bits/stdc++.h>
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;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}

4.8.2 886. 求组合数 II

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤10000,

1≤b≤a≤105

输入样例：

3 1

5 3

2 2

输出样例：

#include<bits/stdc++.h>
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;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
    return 0;
}

4.8.3 887. 求组合数 III

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤20,

1≤b≤a≤1018,

1≤p≤105,

输入样例：

5 3 7

3 1 5

6 4 13

输出样例：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int p;
int qmi(LL a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int C(LL a,LL 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.8.4 888. 求组合数 IV

输入 a,b，求 Cba 的值。

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

输入格式

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

输出格式

共一行，输出 Cba 的值。

数据范围

1≤b≤a≤5000

输入样例：

5 3

输出样例：

#include<bits/stdc++.h>
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--) cout<<res[i];
    return 0;
}

4.8.5 889. 满足条件的01序列

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

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

输入格式

共一行，包含整数 n。

输出格式

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

数据范围

1≤n≤105

输入样例：

输出样例：

#include<bits/stdc++.h>
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;
    cout<<res<<endl;
    return 0;
}

【第四讲】数学知识（2）

4.4 快速幂

4.4.1 875. 快速幂

4.4.2 876. 快速幂求逆元

4.5 扩展欧几里得算法

4.5.1 877. 扩展欧几里得算法

4.5.2 878. 线性同余方程

4.6 中国剩余定理

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

4.7 高斯消元

4.7.1 883. 高斯消元解线性方程组

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

4.8 求组合数

4.8.2 886. 求组合数 II

4.8.3 887. 求组合数 III

4.8.4 888. 求组合数 IV

4.8.5 889. 满足条件的01序列

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【第四讲】 数学知识（2）

4.4 快速幂

4.4.1 875. 快速幂

4.4.2 876. 快速幂求逆元

4.5 扩展欧几里得算法

4.5.1 877. 扩展欧几里得算法

4.5.2 878. 线性同余方程

4.6 中国剩余定理

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

4.7 高斯消元

4.7.1 883. 高斯消元解线性方程组

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

4.8 求组合数

4.8.2 886. 求组合数 II

4.8.3 887. 求组合数 III

4.8.4 888. 求组合数 IV

4.8.5 889. 满足条件的01序列

热门文章

最新文章

相关课程

相关电子书

【第四讲】数学知识（2）