数论

组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1000
#define MOD 100000007
ll c[MAX][MAX];
ll C(int a,int b)
{
    if(c[a][b])
        return c[a][b];
    c[a][b]=(C(a-1,b-1)+C(a-1,b)) % MOD;
    return c[a][b];
}

逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MOD 998244353
// 求快速幂
long long qpow(long long a, int b)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
// 求逆元
long long inv(long long a)//a在MOD下的逆元
{
    return qpow(a, MOD - 2);
}

exgcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ex_gcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = ex_gcd(b, a % b, x, y);
    int temp = y;
    y = x - (a / b) * y;
    x = temp;
    return gcd;
}

求解线性同余方程

ax≡n(modb)ax\equiv n\pmod b 

1
2
3
4
5
6
7
8
9
10
11
12
13
void Equation(int a, int b, int n)
{
    int x, y;
    int d = ex_gcd(a, b, x, y);
    if (n % d != 0)
        return;
    x = x * n / d;
    int r = b / d;
    for (int i = 0; i < d; i++)
    {
        printf("%d\n", (x + i * r) % b);
    }
}

最小正整数解为：

xmin=(x%r+r)%rx_{min}=(x\%r+r)\%r