基礎知識：

　　1.對于任意的ax+by=c， 如果我們知道有一組解x0, y0; 那么 x1 = x0+kb'(b'=b/gcd(a,b)), y1 = y0-ka'(a'=a/gcd(a,b));

　　求解ax + by = c 的過程如下：

　　1.首先我們利用Egcd求出ax+by=g(g = gcd(a,b))的解。 利用此算法我們可以求出三個數g, x, y

　　2.然后我們判斷c%g==0? 如果不等于0， 那么此方程無整數解。如果等于0的時候那么執行第三步

　　3.利用g, x, y, c我們求出ax+by=c的一組解x0 = x*c/g, y0 = y*c/g;

　　4.現在我們利用基礎知識1可以求解出ax+by=c的任意一組解。當求最小的滿足條件的x的時候我們可以利用模運算：

　　實例： POJ1061

　　題意是有兩只青蛙在赤道上跳， 第一只青蛙的起點是x, 每次跳m米， 第二只從y開始每次跳n米， 赤道長度為l， 問兩只青蛙最少幾步相遇？

　　我們可以列出如下方程x+km = y+kn mod(l) => k(m-n) + k1*l = y-x， 代碼如下：

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream>using namespace std; typedef long long LL;void gcd(LL a, LL b, LL &d, LL &x, LL &y) {if(!b) { d=a; x=1; y=0;}else { gcd(b, a%b, d, y, x); y -= x*(a/b); } }int main() {LL x, y, m, n, l;cin>>x>>y>>m>>n>>l;LL a=m-n, b=l, c=y-x;LL g;gcd(a, b, g, x, y);if(c%g != 0){cout<<"Impossible"<<endl;return 0;}LL x0 = c/g*x;//x1 = x0+k*b/gLL bg = b/g>0?b/g:-b/g;x0 = (x0%bg+bg)%bg; //這里使用模運算求解最小值cout<<x0<<endl;return 0; }

?

　　??

轉載于:https://www.cnblogs.com/xingxing1024/p/5189714.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的求解ax + by = c 这类方程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。