相信我,如果你什么东西不会,什么东西不懂,什么东西不记得了,就去尧神模板里找,相信我,你一定能找到!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdlib>
using namespace std;
#define ll long long
ll read(){
ll x=0,y=1;char ch=getchar();
while (isdigit(ch)){if (ch=='-')y=-1;ch=getchar();}
while (!isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*y;
}
//exgcd求逆元,要求a,b互质
ll exgcd(ll a,ll b,ll &x,ll &y){
if (b==0){
x=0,y=1;
return a;
}
ll gcd=exgcd(b,a%b,x,y),tmp;
tmp=x;
x=y,y=tmp-a/b*y;
}
ll cal(ll a,ll b){
ll x,y;
ll gcd=exgcd(a,b,x,y);
if (1%gcd!=0) return -1;
if (b<0)b=-1;
x=(x%b+x)%b;
while (!x) x+=b;
return x;
}
/*
利用费马小定理求逆元,当a,b互质,且b为质数时
由费马小定理得,a^(b-1)=1(mod b)
则有a*a^(b-2)=1(mod b)
那么a^(b-2)就是a在mod b意义下的逆元
*/
ll inv(ll a,ll b){
ll ans=1;
while (b){
if (b&1) ans*=a;
a*=a;b>>=1;
}
return ans;
}
/*
线性递推求逆元,要求p为奇素数
设k=p%i,m=p/i,则有k+m*i=0(mod p)
则-m*i=k
两边同时除以k*i,有
-m*inv[k]=inv[i]
又有:(p-m)*inv[k]=m*inv[k](mod p)
则:inv[i]=(p-p/i)*inv[p%i]%p
*/
ll inv[1000010];
void getinv(){
inv[1]=1;
for (ll i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
}