首页 > 代码库 > 解同余式的最小解
解同余式的最小解
我们知道欧几里得扩展定理是同余方程ax≡b(mod c)解得有力方法。这个方程可能有解也可能没有解,下面给出有解的条件:
定理:同余方程ax≡b(mod c)有解,当且仅当gcd(a,c)|b,且方程有gcd(a,c)个解。
原因是求ax≡b(mod c)可以转化为求ax+cy=b。
令:d=gcd(a,c), k=c/d;
我们可以用扩展欧几里得求出x,y值。那么方程ax≡b(mod c)的一个特解:x0=x*(b/d)%c。并且它的d个解分别为:
Xi=(x0+i*(k))%c,{i=0,1,2,.....d-1}。
方程ax≡b(mod c)的最小解为:(x0%k+k)%k。
代码如下:
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 6 __int64 Exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y) 7 { 8 if(b==0) 9 {10 x=1, y=0;11 return a;12 }13 __int64 r = Exgcd(b, a%b, x, y);14 __int64 tp=x;15 x = y;16 y = tp-a/b*y;17 return r;18 }19 20 // ax==b(mod c)21 void Liner_modu(__int64 a, __int64 b, __int64 c)22 {23 __int64 x, y, ans;24 __int64 d = Exgcd(a, c, x, y);25 if(b%d)26 {27 puts("No solution");28 return;29 }30 ans = x*(b/d)%c; //特解31 y = c / d;32 ans = (ans%y+y)%y; //最小解33 printf("%I64d\n", ans);34 }35 int main()36 {37 __int64 a, b, c;38 while(~scanf("%I64d%I64d%I64d", &a, &b, &c))39 {40 while(a<0) a+=c;41 while(b<0) b+=c;42 Liner_modu(a, b, c);43 }44 return 0;45 }
解同余式的最小解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。