雙六

一個雙六上面向前向后無限延續的格子，每個格子都寫有整數，其中0號格子是起點。1號格子是終點。而骰子上只有a，b，-a，-b四個整數，所以根據a和Bb的值得不同，有可能無法到達終點。
擲出4個整數各多少次可以到達終點呢？如果解不唯一輸出任意一組幾個，如果無解輸出-1。
樣例
輸入
4 11
輸出
3 1
這個問題用數學語言表述就是“求整數x和y使得ax+by=1”。可以發現,如果gcd(a,b≠1,顯然無
解。反之,如果gcd(a,b)=1,就可以通過擴展原來的輾轉相除法來求解。事實上,一定存在整數對(x,y)使得ax+by=gcd(a,b),并可以用同樣的算法求得。設 int extgcd(inta,intb,int&x,int&y)是求解該方程的函數,其返回值是gcd(a,b與gcd一樣,我們可以遞歸地定義 extged。
假設已經求得了
**(a%b)y’=gcd(a, b)
的整數解x和y。再將
a%b=a-(alb)xb
代入后就得到
ay’+b(x’-()xy)=gcd(a, b
而當b=0時則有
a×1+b0=a=gcd(a,b)
將上述數學語言轉化成代碼后,就得到了如下程序。
**

#include<iostream> #include<cstdio> using namespace std; int gcd(int a, int b)//遞歸輾轉相除法求兩個數的最大公因數 {if (b == 0)return a;elsereturn gcd(b, a % b); } void ex_gcd(int a, int b, int& x, int& y)//&是引用，不是地址 {if (b == 0){x = 1;y = 0;return;}else{ex_gcd(b, a % b, x, y);int t = x;x = y;y = t - (a / b) * y;} } int main() {int a, b, x, y;cin >> a >> b;ex_gcd(a, b, x, y);if (gcd(a, b) != 1)cout << -1 << endl;else{cout << x << " " << y << endl;}return 0; }

ax+by=gcd(a，b)的解的大小

只要看一下遞歸的方法就能知道, extged的復雜度和gcd的復雜度是相同的。但該函數所求的
ax+by=gcd(a,b)的解的大小又如何呢?
事實上如果ab≠0,可以知道x≤b且y≤a下面用歸納法來證明這一結論。在b=0的前一步,即a%b=0時有x=0且y=1,結論顯然成立。
假設調用 extgcd(b,a%b,y,x)后有x≤b且ly1≤a%b。
在 extgcd(a,b,x,y)中x=xy=y-(ab)x,所以有如下不等式成立。=≤b,y=y(ab)x≤y+(ab)xx1≤a%b+(a/b)×b=a

總結

以上是生活随笔為你收集整理的扩展欧几里得算法之双六问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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