C++基础数论

前言基础数论怎么这么难啊——————————本文持续更新中——————————逆元众所不周知a*b≡1(mod n)称作b为a的逆元。改一下逆元存在的充分必要条件是 gcd(a,n)1。而其中的充分性就是裴蜀定理可化为拓展欧几里得请看2。接下来我们通过一些题来讲述求逆元的5种方法。以下题意都十分好懂就不放简化了。注一些题可以用多种方法但这里只讲对应方法。1.费马小定理题目传送门费马小定理a^(p-1)≡1(mod p) 其中p为质数a与p互质。适用范围是当模数为质数的情况。接下来是推导过程a^(p-1)≡1(mod p)a*a^(p-2)≡1(mod p)所以a^(p-2)就是a对p的逆元。这里求得时候可以使用快速幂进行解答。然后我们就可以弄出代码#includebits/stdc.h #define int long long using namespace std; const int mod19260817; int pow(int a,int b){ int res1; while(b){ if(b1)resres*a%mod; aa*a%mod; b1; } return res; } int read(){ int res0;char chgetchar(); while(!isdigit(ch)ch!EOF)chgetchar(); while(isdigit(ch)){ res(res3)(res1)(ch-0); res%mod; chgetchar(); } return res; } signed main(){ int a,b; aread(); bread(); if(a(!b)){ printf(Angry!\n); return 0; } printf(%lld\n,a*pow(b,mod-2)%mod); }这也是求逆元最常用的方法。2.拓展gcd题目传送门这个是通解。首先我们要知道P4549 【模板】裴蜀定理众所周知axny1这个方程一定有解。然后可以拓展出axbygcd(a,b)一定有一组解x1,y1使原式成立。然后我们就可以基于这个式子倒推了ax1by1通过上一步可得bx2(a%b)y2接下来需要构造恒等式来求出这一组固定解所以把取模换一种写法写成bx2()y2提一下可得ay2b(x2-*y2)然后我们就可以求出这组解(x1,y1)(y2,x2-*y2)。然后通过gcd算就行了最基层的b0是让(x,y)(1,0)就行了。然后这道题ax mod b1 这个实质就是axbygcd(a,b)原理是方程axbym的有解的必要条件是m mod gcd(a,b)0。而这道题要求最小整数解b又不一定是最小的所以b还要处理一下具体看代码。#includebits/stdc.h using namespace std; #define int long long int x,y; void exgcd(int a,int b){ if(b0){ x1,y0; return; } exgcd(b,a%b); int lxx; xy; ylx-a/b*y; } signed main(){ int a,b; cinab; exgcd(a,b); x(x%bb)%b; printf(%lld\n,x); }3.顺推题目传送门这个适用于一直1~i-1对p的逆元求i的逆元ip。依旧先给结论inv[i]-(p/i)*inv[p%i]下面是推导过程设pkir(一下都是mod p)则pip%i然后得0ip%i随后p%ii两边同除一个i得 p%i*-最后再除一个p%i可得*inv[(p%i)] inv[i]表示i的逆元。然后就得出来了推导按这样写就可以了。代码如下#includebits/stdc.h const long long N20000528; // #define int long long using namespace std; int inv[N],n,p; signed main(){ cinnp; inv[1]1; for(int i2;ip;i) inv[i]1ll*(p-p/i)*inv[p%i]%p; for(int i1;in;i)coutinv[i]\n; }4.逆推题目传送门总而言之就是通过阶乘来求。推导过程因为有如下这个关系inv[i1]两边同乘一个i1: inv[i]inv[i1]*(i1)然后我们就可以求出1~n的所有逆元了。大概就是先求出阶乘然后从后往前按公式求。代码如下#includebits/stdc.h const int N3000005; #define int long long using namespace std; int inv[N],n,p,finv[N],fac[N]; int qpow(int a,int b,int mod){ int res1; while(b){ if(b1)resres*a%mod; aa*a%mod; b1; } return res; } signed main(){ cinnp; fac[0]fac[1]1; for(int i2;in;i) fac[i]fac[i-1]*i%p; finv[n]qpow(fac[n],p-2,p); for(int in-1;i1;i--)finv[i]finv[i1]*(i1)%p; for(int i1;in;i)inv[i]finv[i]*fac[i-1]%p; for(int i1;in;i)coutinv[i]\n; }5.前后缀乘积题目传送门将原式化简为容易看出分子那几项分别可用快速幂、前缀积、后缀积来维护最后在算分母在mod p意义下的逆元就好了可以参考2。代码如下#includebits/stdc.h const unsigned long long N5000005; using namespace std; unsigned long long a[N],n,k,mod,pre[N],suf[N],ans; unsigned long long qpow(unsigned long long a,unsigned long long b,unsigned long long mod){ unsigned long long res1; while(b){ if(b1)resres*a%mod; aa*a%mod; b1; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cinnmodk; unsigned long long nkk; pre[0]suf[n1]1; for(unsigned long long i1;in;i)cina[i]; for(unsigned long long i1;in;i)pre[i]pre[i-1]*a[i]%mod; for(unsigned long long in;i1;i--)suf[i]suf[i1]*a[i]%mod; for(unsigned long long i1;in;i,nknk*k%mod) ans(ansnk*pre[i-1]%mod*suf[i1]%mod)%mod; cout(ans*qpow(pre[n],mod-2,mod))%mod; return 0; }同余维修中.ing结语hhhhh折磨疯了hhhhh