同余问题之模方程模板

2019-04-14 16:08发布

站内文章 / 模拟电子
12887 0 1671
最近看大白书，总结下模板： 快速幂取模 LL pow_mod(LL x,LL a,LL mod) { if(a==0)return 1; LL ans=pow_mod(x,a>>1,mod); ans=ans*ans%mod; if(a&1)ans=ans*x%mod; return ans; }
求逆元 方法1（欧几里得） int rev(int a,int n) { int x,y,d; exgcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } 方法2（欧拉定理） a的逆为pow_mod(a,phi(n)-1,n);
线性同余方程 //形如ax=b(mod n) int mod_equ(int a,int b,int n) { int d=rev(a,n);//求逆元 if(d==-1)return -1; return d*b; }
线性同余方程组 int liner_equs(int n) { int x=0,m=1; for(int i=0;i

离散对数： int log_mod(int a,int b,int n) //a^x=b(mod n)无解返回-1 { int e=1; int m=sqrt(n+0.5); int v=rev(pow_mod(a,m,n),n);//a^(-m) mapx; x[1]=0; for(int i=1;i

热门文章