#创作计划#费马小定理求逆元
2024-10-28 10:48:31
发布于：上海
215阅读
0回复
0点赞
定理
首先我们先要知道费马小定理。费马小定理很简单，只有一句话：
其中 是正整数， 是素数，且 与 互素。
费马小定理最常用于求模意义下的乘法逆元。模意义下的乘法逆元定义为：如果存在一个整数 ，使得 ，则称 为 在模 意义下的逆元。这样在模 的意义下， 就可以被 所替代，而模意义下的乘法比除法简单很多。所以，学会求逆元是很重要的。
我们发现，根据费马小定理，在 是素数，且 与 互素的情况下，。变形得：。因此， 就是 的逆元。这样我们就完成了在 是素数，且 与 互素的情况下的逆元求解。计算时选用快速幂算法，可以实现在 的时间复杂度求解逆元，相当高效。
所以来看题吧。
实战
【模板】有理数取余
（你问我为什么不放“模意义下的乘法逆元”模板题？问就是那题卡费马小定理的复杂度，要用线性推逆元。）
首先，这个数据范围就挺吓人的。但是根据模的性质，我们只需要分子分母（即 ，）在模 意义下的值。所以可以写一个快读，边读边模就行了。
然后，我们开始思考怎么做这题。发现 中，除以 就相当于乘 的逆元，即 。注意到 是个素数，所以求逆元只需要用费马小定理就行了。答案即为 。直接使用快速幂，时间复杂度 。
细节：当 （分母）在模 的意义下为 时，这个分数在模 意义下显然是无意义的。特判输出无解即可。
代码：
#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;
}
总结
费马小定理求逆元相当快。例如求模 的意义下的乘法逆元，数据量为 个数时，本机测试对比如下。
| 费马小定理 | 拓展欧几里得定理 | |
|---|---|---|
| 不开优化 | 12.13500s | 16.81400s |
| 吸氧（O2）（比赛用氧） | 11.88500s | 14.78300s |
| 吸臭氧（O3） | 13.34900s | 18.26300s |
| 吸快氧（Ofast） | 14.18300s | 17.56700s |
为什么有些氧气会有负优化？我也不知道。 不过费马小定理的局限性就在于 不是素数是无法使用。所以各种逆元求法都要学一下。接下来附测试代码。
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;
}
有帮助，赞一个