搜索

数论:同余,逆元,求同余方程,翡蜀定理 - 蓒鳰 -


发布时间: 2022-11-24 18:30:07    浏览次数:45 次

同余表示两个数模上另一个数相同;写作ax=b(mod p),

我们把ax=1(MOD P)  x称为a在p的逆元;

求逆元就是求同余方程

求同余方程使用扩展欧几里得法

 1 int exgcd(int a, int b, int& x, int& y) {
 2     if (b == 0) {
 3         x = 1;
 4         y = 0;
 5         return a;
 6     }
 7     int d = exgcd(a, b, y, x);
 8     y -= (a / b) * x;
 9     return d; 
10 }//返回的d表示a与b的最大公因数,x,y就是同余方程ax+yp=b的最小解;

x=x0+p/gcd(a,p);

y=y0+a/gcd(b,p);

x=(x+b/d)%b/d;

如果b不是d的倍数那么就不成立,成立要乘以b/d;

feishu定理:如果gcd(a,b)=d;

那么ax+by一定是d的倍数,存在x,y使得ax+by=d;

免责声明 数论:同余,逆元,求同余方程,翡蜀定理 - 蓒鳰 - ,资源类别:文本, 浏览次数:45 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:30:07。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/xuanru/p/16736193.html