数学公式整理

欧几里得算法（辗转相除法）

求 $\gcd(a,b)$

int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}

裴蜀定理

P4549 【模板】裴蜀定理

裴蜀定理 $a\times x+b\times y=c$

设 $k=\gcd(a,b)$

$$\therefore k|a,k|b$$ $$\therefore k|a\times x,k|b\times x$$ $$S=\sum_{i=1}^{n}{A_i\times X_i}$$

求最小 $S(S>0)$，$X_i$ 待定。

$$ans=\sum_{i=1}^{n}{\gcd(ans,x_i)}$$

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int r_r(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
int g_d(int a,int b){
	if(a<b)swap(a,b);
	if(!b)return a;
	return g_d(b,a%b); 
}
int main(){
	int n=r_r();
	n-=2;
	int a_s=g_d(abs(r_r()),abs(r_r()));
	while(n--)a_s=g_d(a_s,abs(r_r()));
	printf("%d",a_s);
	return 0;
}

扩展欧几里得算法

求 $a\times x+b\times y=\gcd(a,b)$

void e_g(long long a,long long b,long long &x,long long &y){
	if(!b){
		x=1;y=0;
		return ;
	}
	e_g(b,a%b,y,x);
	y-=(a/b)*x;
}

$x,y$ 即为所求。

同余方程

P1082 NOIP2012 提高组 同余方程

$$a\times x\equiv 1(\mod b)$$ $$a\times x+b\times y=1$$

形式和扩展欧几里得算法很像，此时我们不用管 $y$ 的取值，我们只要找到满足的 $x$ 即可。

并且使 $\gcd(x,y)=1$

求出的 $x$，即为所求。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
long long r_r(){//快读 
	long long k=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return k*f;
}
void e_g(long long a,long long b,long long &x,long long &y){
	if(!b){
		x=1;y=0;
		return ;
	}
	e_g(b,a%b,y,x);
	y-=(a/b)*x;
}
int main(){
	long long a=r_r(),b=r_r(),x,y;
	e_g(a,b,x,y);
	printf("%lld",(x+b)%b);
	return 0;
}

有理数取余

P2613 【模板】有理数取余

$$\frac{a}{b}\mod p$$ $$x\equiv\frac{a}{b}(\mod p)$$ $$b\times x\equiv a(\mod p)$$ $$b\times x_1\equiv 1(\mod p)$$ $$x=x_1\times a$$

注意此时的 $x$ 可能不是最小的，所以要取模处理。

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int m_a=19260817;
long long r_r(){ 
	long long k=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<1)+(k<<3)+(c^48);
		k%=m_a;
		c=getchar(); 
	}
	return k*f%m_a;
}
long long k_m(long long a,long long b){
	long long r_s=1;
	while(b){
		if(b&1)r_s=(r_s*a)%m_a;
		a=(a*a)%m_a;
		b>>=1;
	}
	return r_s%m_a; 
}
int main(){
	long long a=r_r(),b=r_r();
	printf("%lld",a*k_m(b,m_a-2)%m_a);
	return 0;
}

欧拉函数

$\phi(x)=$ 表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数（欧拉函数）。

$$\phi(x)=x\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times …$$

$p_1,p_2,p_3,…$ 是 $m$ 的质因子。

扩展欧拉定理

P5091 【模板】扩展欧拉定理

$$a^b\mod m$$ $$\because a^{\phi(m)}\equiv 1(\mod m)$$ $$\therefore a^b\mod m=a^{b\%\phi(m)+\phi(m)}\mod m$$

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int a,b,m,t_p,m_m,a_s=1;
bool b_b;
int k_m(int a,int b){
	int a_s=1;
	while(b){
		if(b&1)a_s=1LL*a_s*a%m;
		a=1LL*a*a%m;
		b>>=1;
	}
	return a_s;
}
int main(){
    int i;
    char c;
    scanf("%d%d",&a,&m);
    t_p=m_m=m;
    for(i=2;i*i<=m;++i){
        if(t_p%i==0){
            m_m-=m_m/i;
            while(t_p%i==0)t_p/=i;
        }
    }
    if(t_p>1)m_m-=m_m/t_p;
    while(!isdigit(c=getchar()));
    for(;isdigit(c);c=getchar()){
        b=b*10+c-'0';
        if(b>=m_m){
            b_b=true;
            b%=m_m;
        }
    }
    if(b_b)b+=m_m;
	cout<<k_m(a,b)<<endl;
    return 0;
}

费马小定理

可以由欧拉公式推出。

$$a^{p-1}\equiv 1(\mod m)$$

卢卡斯定理

卢卡斯定理/Lucas 定理

$$C_{n+m}^{n}\mod p$$ $$Lucas(n,m,p)=C_{n\%p}^{m\%p}\times Lucas(\frac{n}{p},\frac{m}{p},p)$$ $$Lucas(x,0,p)=1$$ $$C_{a}^{b}=(\frac{a!}{(a-b)!})^{(p-2)}\mod p$$

$p$ 是质数

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
using namespace std;
int k,n,m,p;
long long a[100005],b[100005];
long long lucas(int x,int y)
{
    if(x<y) return 0;
    else if(x<p) return b[x]*a[y]*a[x-y]%p;
    else return lucas(x/p,y/p)*lucas(x%p,y%p)%p;
}
int main()
{
    scanf("%d",&k);
    while(k){
        scanf("%d%d%d",&n,&m,&p);
        a[0]=a[1]=b[0]=b[1]=1;
        for(int i=2;i<=n+m;i++) b[i]=b[i-1]*i%p;
        for(int i=2;i<=n+m;i++) a[i]=(p-p/i)*a[p%i]%p;
        for(int i=2;i<=n+m;i++) a[i]=a[i-1]*a[i]%p;
        printf("%lld\n",lucas(n+m,m));
        k--;
    }
    
    return 0;
}

中国剩余定理（韩信点兵）

P1495 【模板】中国剩余定理(CRT)

$$\left\lbrace \begin{matrix} x\equiv a_1\mod m_1\\ x\equiv a_2\mod m_2\\ x\equiv a_3\mod m_3\\ \vdots\\ x\equiv a_n\mod m_n \end{matrix}\right.$$ $$chj=\prod_{i=1}^{n}{a_i}$$

$x_i$ 通过扩展欧几里得定理求出。

$$ans=\sum_{i=1}^{n}{\frac{chj}{a_i} \times b_i\times x_i}$$

注意取模，$m_i$ 互质。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int r_r(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
const int o_o=1e5+10;
long long a_s;
long long a_a[o_o],b_b[o_o],j_j=1;
void e_g(long long a,long long b,long long &x,long long &y){
	if(!b){
		x=1;
		y=0;
		return ;
	}
	e_g(b,a%b,y,x);
	y-=(a/b)*x;
}
int main(){
	int n=r_r();
	for(int i=0;i<n;i++)a_a[i]=r_r(),b_b[i]=r_r(),j_j*=a_a[i]; 
	for(int i=0;i<n;i++){
		long long n_n=j_j/a_a[i];
		long long x,y;
		e_g(n_n,a_a[i],x,y);
		a_s+=(x%j_j*b_b[i]%j_j*n_n%j_j)%j_j;
	}
	cout<<(a_s+j_j)%j_j<<endl;
	return 0;
}