数论基础

数论基础

1.拓展欧几里得

拓展欧几里得就是求形如$ax+by=\gcd(a,b)$的整数解的一组特解

//ax + by = d
//这个模板中的d = gcd(a, b) 顺便也求出来了
inline void exgcd(int a, int b, int &d, int &x, int &y) {   
    if (!b) d = a, x = 1, y = 0;
    else exgcd(b, a % b, d, y, x), y -= x * (a / b);
}

2.裴蜀定理

对于一个不定方程$ax+by=c$，有整数解的充要条件是$c\mid \gcd(a,b)$

更进一步，有对于不定方程$a_1x_1+a_2x_1+a_3x_3+…+a_n x_n=d$，有整数解的充要条件是$d\mid \gcd(a_1,a_2,…a_n)$

3.线性筛素数

代码中$isPrime[i]$表示i是否是质数，$primes[i]$表示第i小的质数是多少

memset(isPrime, 1, sizeof(isPrime));	
for (int i = 2;i <= N;i++) {
	if (isPrime[i]) 
       	primes[++cnt] = i;
    for (int j = 1;j <= cnt && i * primes[j] <= N;j++) {
        isPrime[i * primes[j]] = false;
        if (i % primes[j] == 0) break;
    }
}

4.求乘法逆元

1.求单个整数的乘法逆元

一般来说我们要求的mod都是一个质数，所以我们可以直接利用$a^{p-2} \equiv 1\pmod p$

int qpow(int a, int b) {
    int ans = 1;
    for (;b;b >>= 1, a = a * a % mod)
        if (a & 1) ans = a * ans % mod;
    return ans;
}
int inv_x = qpow(x, mod - 2);

2.求解一个线性同余方程

求解形如$ax \equiv b \pmod p$的方程

解：$ax \equiv b \pmod p \Rightarrow ax-b=py \Rightarrow ax-py=b \Rightarrow ax+py’=b$

其实就是求解$ax+py=b$这样一个不定方程，用拓展欧几里得实现

3.线性求解n个数的逆元：给你n个整数让你求出他们的逆元

我们设$s[i]=\prod_{i=1}^na[i]$，那么有$s_{i-1}a_i=s_i$，两边同时除$s_{i-1}s_i$，得$a_is_i^{-1}=s_{i-1}^{-1}$，即$a_iinv[s_i]=inv[s_{i-1}]$，

故我们可以线性求出所有的$inv[s[i]]$，同样的我们可以把方程变为$a_i^{-1}=s_{i-1}s_i^{-1}$，即$inv[a_i]=s_{i-1}inv[s_i]$，故我们也可以线性的求出所有$a_i$的逆元

4.线性求解所有$[1,n]$的逆元