C++信息竞赛NOIP各种必备实用模板（逆元，费马小定理，扩展欧几里得，快速幂，卡常，欧拉函数，组合数。。。。。。）
为什么会有此博客？
此博客是为了博主复习时方便地背模板。
博主在代码部分都是默写的，所以可能会有点小错误，见谅。
前半部分重点关注于数论。如果觉得很好的朋友可以收藏了慢慢看
卡常必备！快速读入
int read() {
int s=0,f=1;char a=getchar();
while(a<'0' || a>'9') { if(a=='-') f=-1; a=getchar(); }
while(a>='0' && a<='9') { s=s*10+a-'0'; a=getchar() ; }
return f*s;
}数论基础：扩展欧几里得算法（解二元一次不等式及求最大公因数）
int exgcd (int a,int b ,int& x,int& y) {//函数将返回（gcd(a,b)）
if(b==0) {
x=1,y=0;
return a;
}
int sum=exgcd(b,a%b,y,x)
y-=(a/b)*x;
return sum;
}求逆元（扩展欧几里得法）
int exgcd (int a,int b ,int& x,int& y) {//函数将返回（gcd(a,b)）
if(b==0) {
x=1,y=0;
return a;
}
int sum=exgcd(b,a%b,y,x)
y-=(a/b)*x;
return sum;
}
int inv(int sum,int mod) {//注意：sum与mod必须互质
int x,y;
exgcd(sum,mod,x,y);
return (x%mod+mod)%mod;
}快速幂（求逆元的费马小定理方法用得到）
LL qkpow(LL base,LL indexx)//MOD为模数，题目不要去去掉即可
{
LL sum=1;
while(indexx>0)
{
if(indexx&1)
sum=sum*a%MOD;
base=base*base%MOD;
indexx>>=1;
}
return sum%MOD;
}费马小定理求逆元（MOD要为素数）
LL qkpow(LL base,LL indexx,LL MOD)//改了一下
LL sum=1;
while(indexx>0)
{
if(indexx&1)
sum=sum*a%MOD;
base=base*base%MOD;
indexx>>=1;
}
return sum%MOD;
}
LL inv(LL sum,LL mod) {
return qkpow(sum,mod-2,mod)
}线性递推法求逆元（适用于数据较集中，但模数要为素数）
给一下同校大佬的证明方法
void prepare() {
rfac[0]=rfac[1]=1;
for(int i=2;i<=n;i++)
rfac[i]=1ll*rfac[MOD%i]*(P-P/i)%P;
}
//rfac[i]为i的逆元，MOD必须为质数补充！预处理阶乘的逆元来快速求组合数：
void prepare() {
fac[0]=fac[1]=rfac[0]=rfac[1]=1;
for(int i=2;i<=n;i++) {
fac[i]=1ll*fac[i]*fac[i-1]%MOD;
rfac[i]=1ll*rfac[P%i]*(P-P/i)%P;
}
for(int i=2;i<=n;i++)
rfac[i]=1ll*rfac[i]*rfac[i-1]%P;
}
int C(int n,int m) {
return 1ll*fac[n]*rfac[m]%P*rfac[n-m]%P;
}既然讲到了组合数，那就再多讲一点
Lucas定理模板！
Lucas定理:
int Lucas(int n,int m) {
if(m==0 || m==n) return 1;
return 1ll*C(n%MOD,m%MOD)*Lucas(n/MOD,m/MOD)%MOD;
}补充一个定理，具体实现请看我的博客：
https://blog.****.net/weixin_44049566/article/details/87914975#comments
下面只是组合数的用法，重点是上半部分。
下面有请重点嘉宾：
CRTpro(扩展中国剩余定理）
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100000001
#define LL long long
LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0){
x=1,y=0;
return a;
}
LL sum=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return sum;
}
LL T,m[N],a[N];
int main() {
while(cin>>T) {
LL m1,r1,flag=0;
cin>>m1>>r1;
T--;
while(T--) {
LL x,y,d,m2,r2,tx,sum;
cin>>m2>>r2;
sum=r2-r1;
d=exgcd(m1,m2,x,y);
if(sum%d) flag=1;
x*=sum/d;
tx=(x%(m2/d)+m2/d)%(m2/d);
r1=m1*tx+r1;
m1=m1/d*m2;
}
if(flag) { cout<<-1<<endl; continue; }
cout<<r1<<endl;
}
}具体原理请看我的博客，自以为讲的很详细：
https://blog.****.net/weixin_44049566/article/details/88841843
另一个重点内容：欧拉函数（顺便找出了n以内的素数）
void sieve (int n) {
phi[1]=1;
for(int i=2;i<=n;i++) {
if(!vis[i]) {
prime[++cnt]=i;//找出素数
phi[i]=i;
}
for(int j=1;j<=cnt && i*prime[j] <=n;j++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*phiprime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}上面的适用于数据较小且集中的题，范围大用这个
int phi(int x) {
int p=x;
for(int i=2;i*i<=x;i++) {
if(x%i==0) {
p-=p/i;
while(x%i==0)
x/=i;
}
}
if(x>1) p-=p/x;
return p;
}矩阵乘法
struct Matrix {
LL n,m,c[N][N];
Matrix() { memset(c,0,sizeof(c)); };
void _read() {
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&c[i][j]);
}
Matrix operator * (const Matrix& a) {
Matrix r;
r.n=n;r.m=a.m;
for(int i=1;i<=r.n;i++)
for(int j=1;j<=r.m;j++)
for(int k=1;k<=m;k++)
r.c[i][j]= (r.c[i][j]+ (c[i][k] * a.c[k][j])%mod)%mod;
return r;
}
void _print() {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(j!=1) cout<<" ";
cout<<c[i][j];
}
if(i!=n) puts("");
}
}
Matrix _power(int indexx) {
Matrix tmp,sum;tmp._pre1();sum._pre1();
while(indexx>0) {
if(indexx&1) sum=sum*tmp;
tmp=tmp*tmp;
indexx/=2;
}
return sum;
}
}