前言

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

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

逆元

众所不周知，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;
}

整除

首先知道一些因数的东西。

设n=，于是因数的个数为，因数和。这下还是比较好推的，如果真不会就随便弄个数算一下就好了。

然后接下来需要引出一个东西：欧拉函数φ(n)！

这个函数φ(n)代表n以内与n互质的数的个数。

然后是求法：

1.如果n为质数，那么φ(n)=n-1，因为只有n不与n互质。

2.如果p、q都为指数，那么φ(p*q)=φ(p)*φ(q)=(p-1)*(q-1)。（其实根据欧拉函数是奇性函数就可以得到）

证明过程：
p,2p,3p,....,(q−1)∗p有q−1个数整除p∗q。
同理q,2q,3q,...,(p−1)∗q有p−1个数可以整除pq,再加上pq本身能整除pq，那么丢掉这些数剩余的数就与pq互质，一共有pq−(q−1+p−1+1)=(p−1)(q−1)。

3.如果p是质数，那么φ()=。

证明过程：
p,2p,3p,...,p^(k−1)*p,一共p^(k−1)个数能够整除p^k。
那么丢掉这些数，剩下的p^k-p^(k-1)就与p^k互质。

4.φ(n)=。

这里可以通过2和3推导，这里就不推导了。

代码十分好写，我这个蒟蒻就不写了。。。

然后这些数的和为n*φ(n)/2，记个公式就差不多了。

然后一个诡异的东西降临了——欧拉反演！

浅谈一下，就是∑d|n φ(d)=n。

这个太难推了，我不到啊！

同余

先是定义：如果a%c=b%c，则a≡b (mod c)，可推c|(a-b)。

然后补充一下接下来要用的知识：

如果a+km这个集合对m同余，则这个集合称为模m的同余类。

而0~m-1构成了对m的剩余系，也叫完全剩余系。

结语

hhhhh折磨疯了hhhhh.ing