#创作计划#费马小定理求逆元

userId_undefined

暑 假 神（开学祭

秩序白银

2024-10-28 10:48:31

发布于：上海

168阅读
0回复
0点赞

定理

首先我们先要知道费马小定理。费马小定理很简单，只有一句话：

ap−1≡1 ( mod  p)a^{p-1}\equiv1\ (\bmod\ p)

其中 aa 是正整数，pp 是素数，且 aa 与 pp 互素。

费马小定理最常用于求模意义下的乘法逆元。模意义下的乘法逆元定义为：如果存在一个整数 a−1a^{-1}，使得 a×a−1≡1 ( mod  p)a\times a^{-1}\equiv1\ (\bmod\ p)，则称 a−1a^{-1} 为 aa 在模 pp 意义下的逆元。这样在模 pp 的意义下，÷a\div a 就可以被 ×a−1\times a^{-1} 所替代，而模意义下的乘法比除法简单很多。所以，学会求逆元是很重要的。

我们发现，根据费马小定理，在 pp 是素数，且 aa 与 pp 互素的情况下，a×a−1≡ap−1 ( mod  p)a\times a^{-1}\equiv a^{p-1}\ (\bmod\ p)。变形得：a−1≡ap−2 ( mod  p)a^{-1}\equiv a^{p-2}\ (\bmod\ p)。因此，ap−2mod  pa^{p-2} \mod p 就是 aa 的逆元。这样我们就完成了在 pp 是素数，且 aa 与 pp 互素的情况下的逆元求解。计算时选用快速幂算法，可以实现在 O(log⁡p)O(\log p) 的时间复杂度求解逆元，相当高效。

所以来看题吧。

实战

【模板】有理数取余
（你问我为什么不放“模意义下的乘法逆元”模板题？问就是那题卡费马小定理的复杂度，要用线性推逆元。）
首先，这个数据范围就挺吓人的。但是根据模的性质，我们只需要分子分母（即 aa，bb）在模 1926081719260817 意义下的值。所以可以写一个快读，边读边模就行了。

然后，我们开始思考怎么做这题。发现 abmod  19260817\dfrac ab \mod 19260817 中，除以 bb 就相当于乘 bb 的逆元，即 ab≡a×b−1 ( mod  19260817)\dfrac ab \equiv a\times b^{-1}\ (\bmod\ 19260817)。注意到 1926081719260817 是个素数，所以求逆元只需要用费马小定理就行了。答案即为 a×bp−2mod  19260817a\times b^{p-2}\mod 19260817。直接使用快速幂，时间复杂度 O(log⁡p)O(\log p)。

细节：当 bb （分母）在模 pp 的意义下为 00 时，这个分数在模 pp 意义下显然是无意义的。特判输出无解即可。

代码：

#define Mod 19260817
#define int long long

int powpow(int a,int b){
	int ans=1;
	do{if(b&1)ans=ans*a%Mod;a=a*a%Mod;b>>=1;}while(b);
	return ans;
}

int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),x%=Mod,ch=getchar();
	return x;
}

signed main(){
	int a=read(),b=read();
	if(b==0) puts("Angry!");
	else printf("%lld",a*powpow(b,Mod-2)%Mod);
	return 0;
}

总结

费马小定理求逆元相当快。例如求模 109+710^9+7 的意义下的乘法逆元，数据量为 10710^7 个数时，本机测试对比如下。

费马小定理 拓展欧几里得定理
不开优化 12.13500s 16.81400s
吸氧（O2）（比赛用氧） 11.88500s 14.78300s
吸臭氧（O3） 13.34900s 18.26300s
吸快氧（Ofast） 14.18300s 17.56700s

为什么有些氧气会有负优化？我也不知道。 不过费马小定理的局限性就在于 pp 不是素数是无法使用。所以各种逆元求法都要学一下。接下来附测试代码。

test.h

#include <cstdio>
#include <time.h>

#define FILE
using namespace std;
#define Mod 1000000007
#define int long long

int test=10000000;

int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x;
}

void write(int x){
	if(x>9) write(x/10);
	putchar((x%10)|48);
}

clock_t st,en;
void start(const char* fname){
	#ifdef FILE
	freopen("input.txt","r",stdin);
	freopen(fname,"w",stdout);
	#endif
	st=clock();
}

void end(){
	#ifdef FILE
	fclose(stdin);
	fclose(stdout);
	freopen("CON","w",stdout);
	#endif
	en=clock();
	printf("time = %.5lfs\n",double(en-st)/CLOCKS_PER_SEC);
}

费马小定理

#include "test.h"

int qpow(int a,int b){
	int ans=1;
	do{
		if(b&1) ans=ans*a%Mod;
		a=a*a%Mod;b>>=1;
	}while(b);
	return ans;
}

signed main(){
	start("feima.txt");
	while(test--){
		write(qpow(read(),Mod-2));
		putchar(10);
	}
	end();
	
	return 0;
}

拓展欧几里得定理

#include "test.h"

void exgcd(int a,int b,int&x,int&y){
	if(!b) x=1,y=0;
	else exgcd(b,a%b,y,x),y-=a/b*x;
}

signed main(){
	start("tuoou.txt");
	while(test--){
		int ans=0,tmp;
		exgcd(read(),Mod,ans,tmp);
		ans=(ans%Mod+Mod)%Mod;
		write(ans);
		putchar(10);
	}
	end();
	
	return 0;
}

测试数据生成器

#include <cstdlib>
#include "test.h"

int rand32(){return (rand()<<16)^rand()^(rand()<<16)^rand();}

signed main(){
	srand(time(0));
	start("input.txt");
	while(test--){
		write(rand32());
		putchar(10);
	}
	end();
	
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 13

热门讨论