企业官网建设流程全解析

前言

基础数论怎么这么难啊！！！

——————————本文持续更新中——————————

逆元

众所不周知，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的逆元。

这里求得时候可以使用快速幂进行解答。

然后我们就可以弄出代码：

#include<bits/stdc++.h> #define int long long using namespace std; const int mod=19260817; int pow(int a,int b){ int res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } int read(){ int res=0;char ch=getchar(); while(!isdigit(ch)&&ch!=EOF)ch=getchar(); while(isdigit(ch)){ res=(res<<3)+(res<<1)+(ch-'0'); res%=mod; ch=getchar(); } return res; } signed main(){ int a,b; a=read(); b=read(); if(a&&(!b)){ printf("Angry!\n"); return 0; } printf("%lld\n",a*pow(b,mod-2)%mod); }

这也是求逆元最常用的方法。

2.拓展gcd

题目传送门

这个是通解。

首先我们要知道P4549 【模板】裴蜀定理，众所周知，ax+ny=1这个方程一定有解。

然后可以拓展出ax+by=gcd(a,b)一定有一组解（x1,y1）使原式成立。然后我们就可以基于这个式子倒推了：

ax1+by1通过上一步可得bx2+(a%b)y2，接下来需要构造恒等式来求出这一组固定解，所以把取模换一种写法写成bx2+()y2，提一下可得ay2+b(x2-*y2)，然后我们就可以求出这组解(x1,y1)=(y2,x2-*y2)。

然后通过gcd算就行了，最基层的b=0是让(x,y)=(1,0)就行了。

然后这道题，ax mod b=1 这个实质就是ax+by=gcd(a,b)，原理是方程ax+by=m的有解的必要条件是m mod gcd(a,b)=0。

而这道题要求最小整数解，b又不一定是最小的，所以b还要处理一下，具体看代码。

#include<bits/stdc++.h> using namespace std; #define int long long int x,y; void exgcd(int a,int b){ if(b==0){ x=1,y=0; return; } exgcd(b,a%b); int lx=x; x=y; y=lx-a/b*y; } signed main(){ int a,b; cin>>a>>b; exgcd(a,b); x=(x%b+b)%b; printf("%lld\n",x); }

3.顺推

题目传送门

这个适用于一直1~i-1对p的逆元，求i的逆元（i<p）。

依旧先给结论：inv[i]=-(p/i)*inv[p%i]

下面是推导过程：

设p=ki+r

(一下都是mod p)

则p=i+p%i

然后得0i+p%i

随后p%ii

两边同除一个i得 p%i*-

最后再除一个p%i可得*inv[(p%i)] inv[i]表示i的逆元。

然后就得出来了推导，按这样写就可以了。

代码如下：

#include<bits/stdc++.h> const long long N=20000528; // #define int long long using namespace std; int inv[N],n,p; signed main(){ cin>>n>>p; inv[1]=1; for(int i=2;i<p;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p; for(int i=1;i<=n;i++)cout<<inv[i]<<"\n"; }

4.逆推

题目传送门

总而言之，就是通过阶乘来求。

推导过程：

因为有如下这个关系：inv[i+1]=

两边同乘一个i+1: inv[i]==inv[i+1]*(i+1)

然后我们就可以求出1~n！的所有逆元了。

大概就是先求出阶乘，然后从后往前按公式求。

代码如下：

#include<bits/stdc++.h> const int N=3000005; #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 res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } signed main(){ cin>>n>>p; fac[0]=fac[1]=1; for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%p; finv[n]=qpow(fac[n],p-2,p); for(int i=n-1;i>=1;i--)finv[i]=finv[i+1]*(i+1)%p; for(int i=1;i<=n;i++)inv[i]=finv[i]*fac[i-1]%p; for(int i=1;i<=n;i++)cout<<inv[i]<<"\n"; }

5.前后缀乘积

题目传送门

将原式化简为

容易看出分子那几项分别可用快速幂、前缀积、后缀积来维护，最后在算分母在mod p意义下的逆元就好了（可以参考2）。

代码如下：

#include<bits/stdc++.h> const unsigned long long N=5000005; 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 res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>mod>>k; unsigned long long nk=k; pre[0]=suf[n+1]=1; for(unsigned long long i=1;i<=n;i++)cin>>a[i]; for(unsigned long long i=1;i<=n;i++)pre[i]=pre[i-1]*a[i]%mod; for(unsigned long long i=n;i>=1;i--)suf[i]=suf[i+1]*a[i]%mod; for(unsigned long long i=1;i<=n;i++,nk=nk*k%mod) ans=(ans+nk*pre[i-1]%mod*suf[i+1]%mod)%mod; cout<<(ans*qpow(pre[n],mod-2,mod))%mod; return 0; }

同余

维修中.ing

结语

hhhhh折磨疯了hhhhh