本文共 2095 字,大约阅读时间需要 6 分钟。
文章目录
一、同余
1.求解乘法逆元
要求:实现求乘法逆元的函数,给定a和m,求a模m的乘法逆元,无解时给出无解提示,并且只返回正整数,进而给出求解同余方程(ax=b mod m)的函数,即给定a,b,m,输出满足方程的x,无解给出无解提示。
#includeint egcd(int c,int m){ int b=m; int r1=1,s1=0;//1*c+0*m=c int r2=0,s2=1;//0*c+1*m=m int r=0,t=0,p=0; //r是余数,t是商 r=c%m; while(r!=0) { t=c/m; c=m; m=r;//gcd p=r2; r2=r1-t*r2; r1=p; r=c%m; }//等式右端辗转相除法 if(m!=1)return -1;//如果gcd(c,m)!=1,返回-1 if(r2>0)return r2; else return b+r2; }int main(){ int c,m; scanf("%d %d",&c,&m); if(egcd(c,m)==-1) printf("%d在%d条件下不存在乘法逆元\n",c,m); else printf("%d在%d条件下的乘法逆元是%d\n",c,m,egcd(c,m));}
2.求解同余方程
#includeint congruence(int a,int b,int m){ int w=m; int r1=1,s1=0;//1*c+0*m=c int r2=0,s2=1;//0*c+1*m=m int r=0,t=0,p=0; //r是余数,t是商 r=a%m; while(r!=0) { t=a/m; a=m; m=r;//gcd p=r2; r2=r1-t*r2; r1=p; r=a%m; }//等式右端辗转相除法 if(b/m*m 0)return r2*(b/m); else return (w+r2)*(b/m); }int main(){ int a,b,m; printf("请依次输入a,b,m:\n"); scanf("%d %d %d",&a,&b,&m); if(congruence(a,b,m)==-1) printf("该同余方程没有整数解\n"); else printf("同余方程的解为:%d\n",congruence(a,b,m));}
只有当 b 为 g c d ( a , m ) b为gcd(a,m) b为gcd(a,m)的倍数时,同余方程有整数解,个数为 g c d ( a , m ) gcd(a,m) gcd(a,m)
当gcd(a,m)=1时,方程有一个解二、模指数运算
实现模指数运算函数,给定x,y和m,计算x的y次方模m
#includeint rec_mod_exp(int x,int y,int p){ int z=0; if(y==0) return 1; z=rec_mod_exp(x,y/2,p); if(y==0) return z*z%p; else return x*z*z%p;}
三、费尔马小定理
设p=23,a=5,使用费尔马小定理计算a^{2020}mod p
解: 5 2020 m o d 23 = 5 ( 23 − 1 ) ∗ 91 + 18 m o d 23 5^{2020} mod 23=5^{(23-1)*91+18} mod 23 52020mod23=5(23−1)∗91+18mod23
= 5 18 m o d 23 =5^{18}mod23 =518mod23 = 6 =6 =6
四、欧拉定理
使用欧拉定理计算2^{100000}mod 55。
由于 ϕ ( 55 ) = 40 \phi(55)=40 ϕ(55)=40,由欧拉定理可得 2 100000 m o d 55 = 2 40 ∗ 2500 m o d 55 = 1 2^{100000}mod55=2^{40*2500}mod 55=1 2100000mod55=240∗2500mod55=1
五、手动计算7^{1000}的最后两个数位等于什么
计算 7 1000 7^{1000} 71000的后两位等同于求 7 1000 m o d 100 7^{1000}mod 100 71000mod100
由于 ϕ ( 100 ) = 40 \phi(100)=40 ϕ(100)=40,由欧卡定理可得 7 1000 m o d 100 = 7 40 ∗ 25 m o d 100 = 1 7^{1000}mod 100=7^{40*25}mod100=1 71000mod100=740∗25mod100=1,所以后两位是01
转载地址:https://blog.csdn.net/m0_55443969/article/details/120633763 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!