7.24 同余定理+逆元

2019-04-14 21:09发布

站内文章 / 模拟电子
15448 0 1786

1.同余定理

1.1定义 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他们都有相同的余数1。 数学上的记法为： a≡ b(mod d) 可以看出当n1.2主要性质
数学表述：
加法 (a+b)%c=(a%c+b%c)%c
乘法  (a*c)%c=(a%c*b%c)%c
性质证明(加法)
a = k1*m+r1 ，b = k2*m+r2
(a+b)%m=(( k1*m+r1 )+( k2*m+r2 ))%m
= (( k1+k2 )*m+( r1+r2 ))% m
= (r1+r2 )%m
= (a%m+b%m)% m 1.3应用： 高精度取模     1.3.1高精度对单精度取模     一个高精度数a对一个数b取余，可以把高精度数看成各位数的权值与个位数乘积的和。     比如1234 = ((1 * 10 + 2) * 10 + 3) * 10 + 4，对这个数进行取余运算就是上面基本加和乘的应用。 #include #include using namespace std; int main(){ string a; int b; cin >> a >> b; int len = a.length(); int ans = 0; for(int i = 0; i < len; i++){ ans = (ans * 10 + a[i] - '0') % b; } cout << ans << endl; return 0; }   1.3.2快速幂取模 （详细的快速幂取模https://wenku.baidu.com/view/d65f294702768e9951e73883.html）     将幂拆解为多个底数的平方次的积，如果指数为偶数，把指数除以2，并让底数的平方次取余，如果指数为奇数，就把多出来的底数记录下来，再执行偶数次的操作。 我们先将b按2进制展开假设b = 10, 那么b的二进制为1010，也就是0*2^0+1*2^1+0*2^2+1*2^3 = 10； 所以 a^b = a^(0*2^0+1*2^1+0*2^2+1*2^3 ) = a^(2^1) * a(2^3)；这种简单的转换在初中就学过了吧，相信大家都懂 所以a^b%c = a^(2^1) * a(2^3) % c =( a^(2^1) % c) * (a(2^3)%c)%c； //给出3个正整数A B C，求A^B Mod C。 例如，3 5 8，3^5 Mod 8 = 3。 #include using namespace std; typedef long long ll; ll PowerMod(ll a, ll b, ll c) //快速幂取余 { ll ans = 1; a = a % c; //预处理，防止出现a比c大的情况 while(b) //b=0，return 1 { if(b&1) //最低位为奇数 { ans = (ans *a )% c; } b >>= 1; a = (a * a) % c; } return ans; } int main() { ll a, b, c; cin >> a >> b >> c; cout << PowerMod(a, b, c) << endl; return 0; } 补充：1.同余满足等价关系。具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性(a≡b(mod d),b≡c(mod d))→a≡c(mod d)

2.逆元

定义：设c是b的逆元，则有b*c≡1(mod m)；
推论：(a/b)mod m = (a/b)*1mod m = (a/b)*b*c mod
m=a*c(mod m); 即a/b的模等于a*(b的逆元)的模


2.1费马小定理求解逆元


限制：a，p互质.p为质数
代码实现，复杂度Olog(n) LL pow_mod(LL a, LL b, LL mod){//a的b次方求余p LL ret = 1; while(b){ if(b & 1) ret = (ret * a) % mod; a = (a * a) % mod; b >>= 1; } return ret; } LL Fermat(LL a, LL p){//费马求a关于p的逆元 return pow_mod(a, p-2, p); }  

2.2扩展欧几里得


算法作用：求解a,b 最大公约数m 和a*x+b*y=m 的一个解
实现方法：辗转相除法;
采用递归思想，当b=0时停止递归，此时x=1,y=0;回溯后会
得到一组关于二元一次方程的解 证明
考虑两个方程
:a*x1+b*y1=gcd(a,b),  b*x2 +(a%b)* y2=gcd(b,a%b)
由辗转相除法可得到gcd(a,b)= gcd(b,a%b)
从而得到a*x1+b*y1=b*x2 +(a%b)* y2
即           a*x1+b*y1=b*x2 +(a -(a/b)*b)* y2
                                =a*y2+b*(x2 -(a/b)* y2)
所以x1=y2 ,y1=x2 -(a/b)* y2. a*x≡1(mod m) 等价于a*x+m*y=1 可以用扩展欧几里得求
得一组解，（x+m)mod m即为a的逆元 代码实现 int exgcd (int a, int b, int &x, int &y) { if(b == 0) {//推理，终止条件1 x = 1; y = 0; return a; } int r = exgcd (b, a%b, x, y); int t = y; y = x - (a/b) * y;//相当于y1=x2-(a/b)*y2 x = t; //相当于x1=y2 return r; //最大公约数 } //返回r=gcd(a,b);和对应于等式ax+by=d中的x,y //解x就是a关于b的逆元，解y就是b关于a的逆元 //求2对于1e9+7的逆元就是 exgcd(2, 1e9+7, x, y),其中x的值就是inv2 - a*x + b*y = 1 如果ab互质，有解   这个解的x就是a关于b的逆元 y就是b关于a的逆元 为什么呢？   你看，两边同时求余b   a*x % b + b*y % b = 1 % b a*x % b = 1 % b a*x = 1 (mod b)   你看你看，出现了！！！(/≥▽≤/) 所以x是a关于b的逆元 ----------- #include int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-(a/b)*y; return r; } int main() { int a,b,x,y; scanf("%d %d",&a,&b); int c=exgcd(a,b,x,y);//最大公约数 printf("%d %d ",c,(x+b)%b); return 0; }  

热门文章