淄博网站制作网络定制,关于做网站的问卷调查,网站开发经验与教训范文,wordpress 需要会php文章目录前言数论数学模板GCDexgcd快速幂线性推逆元线性推逆元(非连续)逆元求组合数矩阵乘法线性筛素数-埃氏筛线性筛素数-线性筛线性筛欧拉-埃氏筛线性求欧拉龟速乘FFTNTT分治FFT多项式求逆扩展中国剩余定理Lucas定理高斯消元BSGS拉格朗日插值二次剩余线性基杜教筛前言
因为老…
文章目录前言数论数学模板GCDexgcd快速幂线性推逆元线性推逆元(非连续)逆元求组合数矩阵乘法线性筛素数-埃氏筛线性筛素数-线性筛线性筛欧拉-埃氏筛线性求欧拉龟速乘FFTNTT分治FFT多项式求逆扩展中国剩余定理Lucas定理高斯消元BSGS拉格朗日插值二次剩余线性基杜教筛前言
因为老是懒得打模板的时候老是扣不到自己的标(因为之前的都打得太丑了)所以导致我十分的不爽。便打算开一个模板库。会不断更新的 数论数学模板
(某些附有证明)
GCD
我们设dgcd(a,b)我们设dgcd(a,b)我们设dgcd(a,b) ∵d∣a,d∣b\because d\mid a,d\mid b∵d∣a,d∣b ∴d∣a%b\therefore d\mid a\%b∴d∣a%b 设gcd(b,a%b)d′设gcd(b,a\%b)d设gcd(b,a%b)d′ ∵d′∣b,d′∣a%b\because d\mid b,d\mid a\%b∵d′∣b,d′∣a%b ∴d′∣a\therefore d\mid a∴d′∣a gcd(a,b)gcd(b,a%b)gcd(a,b)gcd(b,a\%b)gcd(a,b)gcd(b,a%b)
int gcd(int a,int b)
{if (b0){return a;}return gcd(b,a%b);
}exgcd
axbygcd(a,b)axbygcd(a,b)axbygcd(a,b) bx′(a%b)y′gcd(b,a%b)bx(a\%b)ygcd(b,a\%b)bx′(a%b)y′gcd(b,a%b) 展开(a%b)(a\%b)(a%b) bx′(a−⌊a/b⌋b)y′gcd(b,a%b)bx(a-\lfloor a/b\rfloor b)ygcd(b,a\%b)bx′(a−⌊a/b⌋b)y′gcd(b,a%b) 拆开括号 bx′ay′−⌊a/b⌋by′gcd(b,a%b)bxay-\lfloor a/b\rfloor bygcd(b,a\%b)bx′ay′−⌊a/b⌋by′gcd(b,a%b) 将aaa和bbb取出 ay′b(x′−⌊a/b⌋y′)gcd(b,a%b)ayb(x-\lfloor a/b\rfloor y)gcd(b,a\%b)ay′b(x′−⌊a/b⌋y′)gcd(b,a%b) ∵gcd(a,b)gcd(b,a%b)\because gcd(a,b)gcd(b,a\%b)∵gcd(a,b)gcd(b,a%b) ∴ay′b(x′−⌊a/b⌋y′)axby\therefore ayb(x-\lfloor a/b\rfloor y)axby∴ay′b(x′−⌊a/b⌋y′)axby 将两边的aaa和bbb取出 y′(x′−⌊a/b⌋y′)xyy(x-\lfloor a/b \rfloor y)xyy′(x′−⌊a/b⌋y′)xy 然后由于两边是等价的 ∴{xy′y(x′−⌊a/b⌋y′)\therefore \left\{\begin{matrix} \\ xy \\ y(x-\lfloor a/b \rfloor y) \\ \\ \end{matrix}\right. ∴⎩⎪⎪⎨⎪⎪⎧xy′y(x′−⌊a/b⌋y′)
#includecstdio
using namespace std;
int x,y,a,b,k;
void gcd(int a,int b)
{if (b0){x1;y0;return;}gcd(b,a%b);kx;xy;yk-a/b*y;return;
}
int main()
{scanf(%d%d,a,b);gcd(a,b);printf(%d,(xb)%b);
}快速幂
ll power(ll x,ll b)
{if(!b) return 1;ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}线性推逆元
首先对于p我们将其分解为kir(k⌊pi⌋,rp%r)kir(k\lfloor \frac{p}{i}\rfloor,rp\%r)kir(k⌊ip⌋,rp%r)然后有 kir≡0(modp)kir\equiv 0(mod\ \ p)kir≡0(mod p) 左右两边同时乘上一个i−1∗r−1i^{-1}*r^{-1}i−1∗r−1 k∗r−1i−1≡0(modp)k*r^{-1}i^{-1}\equiv 0(mod\ \ p)k∗r−1i−1≡0(mod p) i−1≡−k∗r−1(modp)i^{-1}\equiv -k*r^{-1}(mod\ \ p)i−1≡−k∗r−1(mod p) i−1≡−⌊pi⌋∗(p%i)−1(modp)i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor*(p\%i)^{-1}(mod\ \ p)i−1≡−⌊ip⌋∗(p%i)−1(mod p) 反正本来就要%p\%p%p i−1−⌊pi⌋∗(p%i)−1%pi^{-1} -\lfloor \frac{p}{i}\rfloor*(p\%i)^{-1}\%pi−1−⌊ip⌋∗(p%i)−1%p 因为iii比(p%i)(p\%i)(p%i)小按照递推的顺序我们在求出i−1i^{-1}i−1之前就已经求出(p%i)−1(p\%i)^{-1}(p%i)−1了。但是我们还要保证不是负数所以我们可以直接计算 i−1p−⌊pi⌋∗(p%i)−1%pi^{-1} p-\lfloor \frac{p}{i}\rfloor*(p\%i)^{-1}\%pi−1p−⌊ip⌋∗(p%i)−1%p
#includecstdio
using namespace std;
int n,p;
long long inv[3000010];
int main()
{scanf(%d%d,n,p);inv[1]1;printf(%d\n,inv[1]);for(int i2;in;i)inv[i](long long)p-p/i*inv[p%i]%p,printf(%d\n,inv[i]);
}线性推逆元(非连续)
#includecstdio
#includecstring
#includecctype
#includealgorithm
#define ll long long
using namespace std;
const ll N5e610;
ll n,p,K,S,a[N],s[N],k[N],ans;
__attribute__((optimize(O3))) inline int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
ll power(ll x,ll b,ll p)
{ll ans1;while(b){if(b1) ansans*x%p;xx*x%p;b1;}return ans;
}
int main()
{nread();pread();Kread();S1;k[0]1;s[0]1;for(int i1;in;i){a[i]read();SS*a[i]%p;s[i]S;k[i]k[i-1]*K%p;}Spower(S,p-2,p);for(int in;i1;i--){ll invS*s[i-1]%p;SS*a[i]%p;(ansk[i]*inv%p)%p;}printf(%lld,ans);
}
逆元求组合数
ll power(ll x,ll b)
{ll ans1;x%XJQ;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
ll C(ll n,ll m)
{ll ans11,ans21;for(ll in-m1;in;i)ans2ans2*i%XJQ;for(ll i1;im;i)ans1ans1*power(i,XJQ-2)%XJQ;return ans2*ans1%XJQ;
}矩阵乘法
struct matrix{ll a[size][size];
}f;
matrix operator *(matrix a, matrix b) {matrix c;memset(c.a,0,sizeof(c.a));for (ll i0;isize;i)for (ll j0;jsize;j)for (ll k0;ksize;k)(c.a[i][j]a.a[i][k]*b.a[k][j])%YMW;return c;
}
void ksm(matrix f,ll b) {matrix af;while(b){if(b1) aa*f;ff*f;b1;}fa;
}线性筛素数-埃氏筛
void primes()
{for(ll i2;iN;i)if(!v[i]){prime[cnt]i;s[i]1;//素数也标记for(ll j2;i*jN;j){if(!v[j]ji)//是素数的乘积s[i*j]1;v[i*j]true;}}
}线性筛素数-线性筛
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m,cnt,prime[6893911];
bool v[10000001];
int main()
{scanf(%d%d,n,m);v[1]1;for(int i2;in;i){if(!v[i]) prime[cnt]i;for(int j1;jcnti*prime[j]n;j){v[prime[j]*i]1;if(!(i%prime[j])) break;}}for(int i1;im;i){int x;scanf(%d,x);if(v[x]) printf(No\n);else printf(Yes\n);}
}线性筛欧拉-埃氏筛
for (int i2;in;i) phi[i]i;//初始化欧拉
for (int i2;in;i)
{if (phi[i]i)//质数for (int ji;jn;ji)phi[j]phi[j]/i*(i-1);//筛去一个质因子sumphi[i];//统计答案
}线性求欧拉
ll phi(ll n)//求欧拉函数
{ll ansn;for (ll i2;i*in;i)if (n%i0){ansans/i*(i-1);while (n%i0) n/i;}if (n1) ansans/n*(n-1);return ans;
}龟速乘
ll ksc(ll a,ll b)
{a%YMW;b%YMW;ll c(long double)a*b/YMW;ll ansa*b-c*YMW;if(ans0) ansYMW;else if(ansYMW) ans-YMW;return ans;
}FFT
#includecstdio
#includealgorithm
#includecstring
#includecmath
using namespace std;
const int N1e6100;
const double Piacos(-1);
int n,m,l,r[N2];
struct complex{complex(double xx0,double yy0){xxx;yyy;} double x,y;
}f[N2],g[N2];
complex operator (complex a,complex b)
{return complex(a.xb.x,a.yb.y);}
complex operator -(complex a,complex b)
{return complex(a.x-b.x,a.y-b.y);}
complex operator *(complex a,complex b)
{return complex(a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x);}
void fft(complex *f,int op)
{for(int i0;in;i)if(ir[i]){complex tmpf[i];f[i]f[r[i]];f[r[i]]tmp;}for(int p2;pn;p1){int lenp1;complex tmpcomplex(cos(Pi/len),sin(Pi/len)*op);for(int k0;kn;kp){complex buf(1,0);for(int ik;iklen;i){complex ttbuf*f[leni];f[leni]f[i]-tt;f[i]f[i]tt;bufbuf*tmp;}}}
}
int main()
{scanf(%d%d,n,m);for(int i0;in;i)scanf(%lf,f[i].x);for(int i0;im;i)scanf(%lf,g[i].x);for(mn,n1;nm;n1);for(int i0;in;i)r[i](r[i1]1)|((i1)?n1:0);fft(f,1);fft(g,1);for(int i0;in;i)f[i]f[i]*g[i];fft(f,-1);for(int i0;im;i)printf(%.0lf ,fabs(f[i].x)/n);
}NTT
#includecstdio
#includealgorithm
#includecstring
#includecmath
#define ll long long
using namespace std;
const ll N1e6100,XJQ998244353,G3,Gi332748118;
const double Piacos(-1);
ll n,m,l,r[N2],f[N2],g[N2];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void ntt(ll *f,ll op)
{for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(op1?G:Gi,(XJQ-1)/p);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[leni]%XJQ;f[leni](f[i]-ttXJQ)%XJQ;f[i](f[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}
}
int main()
{scanf(%lld%lld,n,m);for(ll i0;in;i) scanf(%lld,f[i]);for(ll i0;im;i) scanf(%lld,g[i]);for(mn,n1;nm;n1);for(ll i0;in;i)r[i](r[i1]1)|((i1)?n1:0);ntt(f,1);ntt(g,1);for(ll i0;in;i)f[i]f[i]*g[i]%XJQ;ntt(f,-1);ll invpower(n,XJQ-2);for(ll i0;im;i)printf(%lld ,f[i]*inv%XJQ);
}分治FFT
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,XJQ998244353;
ll n,g[N],f[N],a[N],b[N],R[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;b1;xx*x%XJQ;}return ans;
}
void NTT(ll *f,ll logn,ll op){ll n1logn;for(ll i0;in;i)if(iR[i])swap(f[i],f[R[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(XJQ-1)/p);if(op-1)tmppower(tmp,XJQ-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[leni]%XJQ;f[leni](f[i]-ttXJQ)%XJQ;f[i](f[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op-1){ll tmppower(n,XJQ-2);for(ll i0;in;i)f[i]f[i]*tmp%XJQ;}return;
}
void cdq(ll l,ll r,ll logn){if(!logn) return;if(ln)return;ll n1logn,midlr1;cdq(l,mid,logn-1);for(ll i0;in;i)R[i](R[i1]1)|((i1)?n1:0);memset(a(r-l)/2,0,sizeof(ll)*(r-l)/2);memcpy(a,fl,sizeof(ll)*(r-l)/2);memcpy(b,g,sizeof(ll)*(r-l));NTT(a,logn,1);NTT(b,logn,1);for(ll i0;in;i)a[i]a[i]*b[i]%XJQ;NTT(a,logn,-1);for(ll i(r-l)/2;ir-l;i)f[li](f[li]a[i])%XJQ;cdq(mid,r,logn-1);return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,g[i]);f[0]1;ll logn;for(logn0;(1logn)n;logn);cdq(0,1logn,logn);for(ll i0;in;i)printf(%lld ,(f[i]XJQ)%XJQ);
}
多项式求逆
// luogu-judger-enable-o2
#includecstdio
#includealgorithm
#includecstring
#includecmath
#define ll long long
using namespace std;
const ll N1e6100,XJQ998244353,G3,Gi332748118;
const double Piacos(-1);
ll n,m,l,a[N2],b[N2],c[N2],r[N2];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void ntt(ll *f,ll n,ll op)
{for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(G,(XJQ-1)/p);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[leni]%XJQ;f[leni](f[i]-ttXJQ)%XJQ;f[i](f[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op1) return;int invpower(n,XJQ-2);reverse(f1,fn);for(int i0;in;i) f[i]f[i]*inv%XJQ;
}
void work(ll *a,ll *b,ll l)
{if(l1){b[0]power(a[0],XJQ-2);return;}work(a,b,(l1)1);ll cnt;for(cnt1;cnt(l1);cnt1);for(ll i1;icnt;i)r[i](r[i1]1)|((i1)?cnt1:0);for(ll i0;il;i) c[i]a[i];for(ll il;icnt;i) c[i]0;ntt(c,cnt,1);ntt(b,cnt,1);for(ll i0;icnt;i)b[i](2-b[i]*c[i]%XJQXJQ)%XJQ*b[i]%XJQ;ntt(b,cnt,-1);for(ll il;icnt;i) b[i]0;
}
int main()
{scanf(%lld,n);for(ll i0;in;i)scanf(%lld,a[i]);work(a,b,n);for(ll i0;in;i)printf(%lld ,b[i]);
}扩展中国剩余定理
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e5100;
ll n,a[N],b[N],ans;
ll ksc(ll a,ll b,ll YMW)
{a%YMW;b%YMW;ll c(long double)a*b/YMW;ll ansa*b-c*YMW;if(ans0) ansYMW;else if(ansYMW) ans-YMW;return ans;
}
ll exgcd(ll a,ll b,ll x,ll y)
{if(!b){x1;y0;return a;}ll dexgcd(b,a%b,x,y),zx;xy;yz-a/b*y;return d;
}
void work()
{ll x,y,k,Mb[1];ansa[1];for(ll i2;in;i){ll AM,Bb[i],c(a[i]-ans%BB)%B;ll dexgcd(A,B,x,y),gB/d;if(c%d){ans-1;return;}xksc(x,c/d,g);ansx*M;M*g;ans(ans%MM)%M;}
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld%lld,b[i],a[i]);work();printf(%lld,ans);
}Lucas定理
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll T,n,m,p,a[110000];
ll power(ll x,ll b,ll p)
{ll ans1;while(b){if(b1) ansans*x%p;xx*x%p;b1;}return ans;
}
ll C(ll n,ll m,ll p)
{if(mn) return 0ll;return a[n]*power(a[m],p-2,p)%p*power(a[n-m],p-2,p)%p;
}
ll lucas(ll n,ll m,ll p)
{if(!m) return 1ll;return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main()
{scanf(%lld,T);while(T--){scanf(%lld%lld%lld,n,m,p);a[0]1;for(ll i1;ip;i)a[i]a[i-1]*i%p;printf(%lld\n,lucas(nm,m,p));}return 0;
} 高斯消元
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N110;
int n;
double b[N],c[N][N];
int main()
{scanf(%d,n);for(int i1;in;i){for(int j1;jn;j)scanf(%lf,c[i][j]);scanf(%lf,b[i]);}for(int i1;in;i){int zi;for(int ji1;jn;j){if(fabs(c[j][i])fabs(c[z][i]))zj;}for(int j1;jn;j)swap(c[i][j],c[z][j]);swap(b[i],b[z]);if(!c[i][i]){printf(No Solution\n);return 0;}for(int j1;jn;j){if(ij) continue;double ratec[j][i]/c[i][i];for(int ki;kn;k)c[j][k]-c[i][k]*rate;b[j]-b[i]*rate; }}for(int i1;in;i)printf(%.2lf\n,b[i]/c[i][i]);
}BSGS
#includecstdio
#includealgorithm
#includecstring
#includecmath
#includemap
#define ll long long
using namespace std;
ll p,b,n,ans1e18,t;
mapll,ll v;
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%p;xx*x%p;b1;}return ans;
}
int main()
{scanf(%lld%lld%lld,p,n,b);t(int)sqrt(p)1;for(ll i0;it;i){ll valb*power(n,i)%p;v[val]i;}npower(n,t);if(n0) {if(!b) printf(1);else printf(no solution);return 0;}for(ll i0;it;i){ll valpower(n,i);ll jv.find(val)v.end()?-1:v[val];if(j0i*t-j0) ansmin(ans,i*t-j);}if(ans1e18) printf(no solution);else printf(%lld,ans);
}
拉格朗日插值
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e310,XJQ998244353;
ll n,k,x[N],y[N],ans;
ll power(ll x,ll b){x%XJQ;ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
int main()
{scanf(%lld%lld,n,k);for(ll i1;in;i)scanf(%lld%lld,x[i],y[i]);for(ll i1;in;i){for(ll j1;jn;j)if(i!j)(y[i]*(k-x[j]XJQ)%XJQ*power(x[i]-x[j]XJQ,XJQ-2)%XJQ)%XJQ;(ansy[i])%XJQ; }printf(%lld,ans);
}
二次剩余
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll T,n,p,k,w;
struct complex{complex(ll xx0,ll yy0){xxx;yyy;}ll x,y;
};
complex operator(complex a,complex b)
{return complex((a.xb.x)%p,(a.yb.y)%p);}
complex operator-(complex a,complex b)
{return complex((a.x-b.xp)%p,(a.y-b.yp)%p);}
complex operator*(complex a,complex b)
{return complex((a.x*b.x%pa.y*b.y%p*w%pp)%p,(a.x*b.ya.y*b.x)%p);}
complex poweri(complex x,ll b){complex anscomplex(1,0);while(b){if(b1)ansans*x;xx*x;b1; }return ans;
}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%p;xx*x%p;b1;}return ans;
}
bool check(ll a)
{return power(((a*a%p-n)%pp)%p,k)(p-1);}
int main()
{srand(31958);scanf(%lld,T);while(T--){scanf(%lld%lld,n,p);if(!n){printf(0\n);continue;}if(p2){printf(%lld\n,n);continue;}k(p-1)1;if(power(n,k)p-1){printf(Hola!\n);continue;}ll arand()%p;while(!check(a))arand()%p;w((a*a%p-n)%pp)%p;ll x1poweri(complex(a,1),(p1)/2).x;ll x2p-x1;if(x1x2)swap(x1,x2);if(x1!x2)printf(%lld %lld\n,x1,x2);else printf(%lld\n,x1);}
}
线性基
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll n,d[60];
void add(ll x){for(ll i51;i0;i--){if(x(1lli)){if(d[i])x^d[i];else{d[i]x;break;}}}return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x;scanf(%lld,x);add(x);}ll ans0;for(ll i51;i0;i--)if(ans(ans^d[i]))ansans^d[i];printf(%lld,ans);
}
杜教筛
#includecstdio
#includecstring
#includealgorithm
#includemap
#define ll long long
using namespace std;
const ll N1e71;
ll T,n,cnt,mu[N],phi[N],pri[N];
bool vis[N];
mapll,ll sp,sm;
void prime(){mu[1]phi[1]1;for(ll i2;iN;i){if(!vis[i])pri[cnt]i,mu[i]-1,phi[i]i-1;for(ll j1;jcntpri[j]*iN;j){vis[pri[j]*i]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}phi[i*pri[j]]phi[pri[j]]*phi[i];mu[i*pri[j]]-mu[i];}}for(ll i1;iN;i)phi[i]phi[i-1],mu[i]mu[i-1];return;
}
ll GetSphi(ll n){if(nN)return phi[n];if(sp[n])return sp[n];ll restn*(n1ll)/2ll;for(ll l2ll,r;ln;lr1ll)rn/(n/l),rest-(r-l1ll)*GetSphi(n/l);return (sp[n]rest);
}
ll GetSmul(ll n){if(nN)return mu[n];if(sm[n])return sm[n];ll rest1ll;for(ll l2ll,r;ln;lr1ll)rn/(n/l),rest-(r-l1ll)*GetSmul(n/l);return (sm[n]rest);
}
int main()
{scanf(%lld,T);prime();while(T--){scanf(%lld,n);printf(%lld %lld\n,GetSphi(n),GetSmul(n));}
}
