POJ 1061 BZOJ 1477 Luogu P1516 青蛙的約會 (擴展歐幾里得算法)

手動博客搬家: 本文發表于20180226 23:35:26, 原地址https://blog.csdn.net/suncongbo/article/details/79382991

題目鏈接: (poj)http://poj.org/problem?id=1061
(bzoj)http://www.lydsy.com/JudgeOnline/problem.php?id=1477
(Luogu)https://www.luogu.org/problemnew/show/P1516
數據強度對比: 在以上三個OJ中，本題Luogu數據最強。使用一種錯誤代碼在BZOJ與POJ均能AC，而Luogu無法AC.

題目大意:
求解方程\[u+mx\equiv v+nx (\mod p)\]注意這里的u,v,m,n,p分別對應題目中的x,y,n,m,L.

思路分析:
解同余方程？很經典的使用exgcd算法的問題。(簡單一點的exgcd解同余方程的題目可參照luogu P1082 NOIP 2012 D2 T1 同余方程，題目鏈接https://www.luogu.org/problem/show?pid=1082)
一般來說，如果是形如\(ax\equiv c(\mod b)\)的同余方程都可化為\(ax+by=c\)的形式，用exgcd算法求解后\(x\)的值即為原方程的解。
所以直接化一化式子即可: \[u+mx\equiv v+nx(\mod p)\]\[u+mx-v-nx\equiv 0(\mod p)\]\[(m-n)x\equiv v-u(\mod p)\]代入上面的公式，令\(a=m-n, c=v-u, b=p\)可得答案即為不定方程\[(m-n)x+py=v-u\]的所有解中x最小且為整數的解的x值.
注意討論正數與負數的情況。現假設\(m>n\).
如果\(\gcd(m-n,p)\)不整除\(|v-u|\)(注意v不一定大于u), 則無解
否則直接exgcd即可。求出\[(m-n)x+py=gcd(m-n,p)\]的一組解，乘以\(\frac{v-u}{gcd(m-n,p)}\)(注意不加絕對值)即可. 于是我們求出了特解。
如何求x>0且最小的解呢? 我們發現若\(ax+by=c\)特解為\(x=x_0, y=y_0\)則通解為\(x=x_0+\frac{gcd(a,b)}t, y=y_0-\frac{a}{gcd(a,b)}t\)(t取任意整數)(一定注意不要忘記除以gcd!!!)因此在數學上對\(\frac{gcd(a,b)}\)取模即可。
注意此處“在數學上”\(A \mod B\)是指\(A\equiv X (\mod B)\)且\(0\le X\lt b\)的唯一的X, 但是在C++語言編程中不能這樣取模，C++中負數取模的含義是

(-A) % B == -(A % B) (A>0,B>0)

例如

(-6) % 5 = -1 (-7) % 4 = -3 (-18) % 9 = 0

其返回值\(x\)滿足\(-B\lt x\le 0\)
因此在數學上負整數\(-A\)對正整數\(B\)取模，就相當于在C++語言中的

(((-A)%B)+B)%B

(注: 以上關于取模的分析過程均采用大寫，關于不定方程的分析過程均采用小寫)
代入\(-A=x_0, B=\frac{gcd(a,b)}\)即可，再將a,b分別換成原方程中的\(m-n\)和\(p\)，直接暢通無阻地使用exgcd即可。

部分易錯點

很容易炸long long, 一定注意。

代碼實現
(三個OJ均AC)

#include<cstdio> #include<algorithm> using namespace std;long long u,v,m,n,p;long long exgcd(long long a,long long b,long long &x,long long &y) {if(b==0ll) {x = 1ll; y = 0ll; return a;}long long ret = exgcd(b,a%b,y,x); y -= a/b*x;return ret; }long long gcd(long long a,long long b) {if(b==0ll) return a;else return gcd(b,a%b); }long long absl(long long x) {return x>0ll ? x : -x; }void swap_ll(long long &x,long long &y) {long long c = x; x = y; y = c; }int main() {scanf("%lld%lld%lld%lld%lld",&u,&v,&m,&n,&p);long long x,y;if(m==n) {puts("Impossible"); return 0;}if(m-n<0) {swap_ll(u,v); swap_ll(m,n);}if(absl(v-u)%gcd(m-n,p)!=0) {puts("Impossible"); return 0;}exgcd(m-n,p,x,y);long long s = x*((v-u)/gcd(m-n,p)); //此處一定是用(v-u)/gcd(m-n,p),x不一定被gcd整除long long g = p/gcd(m-n,p); //把g直接當成了p使用，在BZOJ和POJ居然AC，所幸Luogu WAs = ((s%g)+g)%g;printf("%lld\n",s);return 0; } 發表于 2018-12-30 11:44 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

總結

以上是生活随笔為你收集整理的POJ 1061 BZOJ 1477 Luogu P1516 青蛙的约会 (扩展欧几里得算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

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