C++基础数论

adminh_miao

89人浏览 · 2026-05-22 22:15:02

adminh_miao · 2026-05-22 22:15:02 发布

前言

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

逆元

众所不周知，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+( $a- \left \lfloor \frac{a}{b} \right \rfloor*b$ )y2，提一下可得ay2+b(x2- $\left \lfloor \frac{a}{b} \right \rfloor$ *y2)，然后我们就可以求出这组解(x1,y1)=(y2,x2- $\left \lfloor \frac{a}{b} \right \rfloor$ *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= $\left \lfloor \frac{p}{i} \right \rfloor$ i+p%i

然后得0 $\equiv \left \lfloor \frac{p}{i} \right \rfloor$ i+p%i

随后p%i $\equiv -\left \lfloor \frac{p}{i} \right \rfloor$ i

两边同除一个i得 p%i* $i^{-1}$ $\equiv$ - $\left \lfloor \frac{p}{i} \right \rfloor$

最后再除一个p%i可得 $i^{-1}\equiv -\left \lfloor \frac{p}{i} \right \rfloor$ *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]= $\frac{1}{(i+1)!}$

两边同乘一个i+1: inv[i]= $\frac{1}{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.前后缀乘积

题目传送门

将原式化简为 $\frac{\sum_{i=1}^{n} k^{i}*\prod_{j=1}^{i-1}b_{j}*\prod_{j=i+1}^{n}b_{j}}{\prod_{i=1}^{n}a_{i}} mod p$

容易看出分子那几项分别可用快速幂、前缀积、后缀积来维护，最后在算分母在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= $p_{1}^{a_{1}}*p_{2}^{a_{2}}*...p_{x}^{a_{x}}$ ，于是因数的个数为 $\left ( a_{1}+1 \right )\left ( a_{2}+1 \right )...\left ( a_{x}+1 \right )$ ，因数和。这下还是比较好推的，如果真不会就随便弄个数算一下就好了。

然后接下来需要引出一个东西：欧拉函数φ(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^{k}$ )= $p^{k}-p^{k-1}$ 。

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

4.φ(n)= $\left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )...\left ( 1-\frac{1}{p_{x}} \right )$ 。

这里可以通过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的剩余系，也叫完全剩余系。

比如上面的φ(n)就构成了简化剩余系，也对乘法封闭。

然后就可以引出一个~~美妙的~~定理——欧拉定理！

内容：a^φ(n) $\equiv$ 1(mod n) 此时a与n互质。

证明过程：

首先我们把φ(n)这个序列乘以一个a，可得a*x[i] $\equiv$ a*x[j](mod n)。

移过来，a*(x[i]-x[j]) $\equiv$ 0(mod n)。这里顺便证了一下是简化剩余系。

a^φ(n)*x[1]*x[2]*...*x[φ(n)]此时=ax[1]*ax[2]*...*ax[φ(n)] $\equiv$ x[1]*x[2]*...*x[φ(n)]。

连立一三项，然后就证明完毕啦！

还有一个~~可爱的~~费马小定理。

内容：a^(p-1) $\equiv$ 1(mod p) 前提a与p互质，p为质数。

证明过程：

跟欧拉有点像，a^(p-1)*1*2*...*(p-1)=(a*1)*(a*2)*...*(a*(p-1))。

于是a*i $\equiv$ a*j(mod p)，a(i-j) $\equiv$ 0(mod p)。

所以原式 $\equiv$ 1*2*...*(p-1) (mod p)。

连立一三项，然后就证明完毕啦！

还有一个拓展欧拉定理，这里就不讲解了。

然后有一个~~伟大的~~定理，叫做中国剩余定理！

题面：

求解以下同余方程的最小整数解，其中b[1-n]为两两互质的整数。

$\begin{Bmatrix} x\equiv a[1](mod b[1])\\ x\equiv a[2](mod b[2])\\ ... \\ x\equiv a[n](mod b[n]) \end{Bmatrix}$

利用中国剩余定理，步骤如下：

计算所有模数b[i]的乘积M
计算c[i]=M/b[i]
计算c[i]在模b[i]意义下的乘法逆元
计算ans= $\sum_{n}^{i=1} a[i]\times c[i]\times c[i]^{-1}(mod M)$

这就是用法，首先证明ans对于每一个j都满足原式，证明如下：

当i！=j时，c[j]包含因数c[i]，所以 $c[j]\equiv 0(mod b[j])$ ，所以 $a[j]\times c[j]\times c[j]^{-1}\equiv 0(mod b[j])$ 也成立
当i==j时，c[j]不包含因数c[i]，又因为 $c[j]\times c[j]^{-1}\equiv 1(mod b[j])$ ，所以 $a[j]\times c[j]\times c[j]^{-1}\equiv a[j](mod b[j])$

得证。

其次，对于每一个m[j]来说，mod M相当于减去m[j]的若干倍，不会影响余数a[j]的结果。

然后我们放心大胆就可以使用拓展欧几里得算法（在上面）计算逆元，最后贴个代码吧！

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n,a[15],b[15],c,M=1,xx,yy,ans;
void exgcd(int a,int b){
	if(!b){xx=1,yy=0;return ;}
	exgcd(b,a%b);
	int t=xx;
	xx=yy;
	yy=t-a/b*xx;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
		M*=a[i];
	}
	for(int i=1;i<=n;i++){
		c=M/a[i];
		exgcd(c,a[i]);
		ans=((ans+c*xx*b[i])%M+M)%M;
	}
	printf("%lld\n",ans);
}

结语

hhhhh折磨疯了hhhhh.ing

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

Qt 冷门但致命：nativeEvent() 到底动了谁的奶酪？

nativeEvent() 是 Qt 提供的‌拦截并处理操作系统底层原生消息‌的钩子函数，用于在 Qt 事件系统之外直接访问平台特定事件（如 Windows MSG、X11 XEvent、macOS NSEvent）。‌‌

openEuler 社区

Beedup 数据库实时复制软件｜全信创适配，低侵入异构实时同步一体化方案

openEuler 社区

数据中心电力模块的发展前景：从预制化集成到智能能源路由的演进路径

开发门槛上，灵基构建了Chat、Work、Build三级能力体系：Chat面向自然语言交互与知识问答，Work聚焦岗位级智能体执行与协同，Build提供企业级应用与Agent的原生开发环境，覆盖从"对话使用"到"岗位运行"再到"能力创造"的全链路。面对国内AI智能体服务商已突破300家的供给端膨胀，企业选型的核心问题已从"要不要用"转向"选哪家、怎么选、怎么管"。金蝶灵基的核心定位是企业AI原生操