生活随笔
收集整理的這篇文章主要介紹了
杭电2669拓展欧几里得
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
杭電2669
給a,b求Xa Yb = 1.如果沒有則輸出sorry。
可以通過拓展歐幾里得指導(dǎo)Xa Yb = gcd(a,b).
不言而喻要判斷gcd(a,b)是否等于1.如果不等于1，那么就是sorry。如果等于一，那么還不能讓x小于0，要對(duì)x,y進(jìn)行加減操作滿足x>0；拓展歐幾里得是通過遞歸從下往上進(jìn)行運(yùn)算。
import java
.io
.BufferedReader
;
import java
.io
.IOException
;
import java
.io
.InputStreamReader
;
import java
.io
.OutputStreamWriter
;
import java
.io
.PrintWriter
;
import java
.io
.StreamTokenizer
;
public class hdu2669 {static long x
=0;static long y
=0;public static void main(String
[] args
) throws IOException
{StreamTokenizer in
=new StreamTokenizer(new BufferedReader(new InputStreamReader(System
.in
)));PrintWriter out
= new PrintWriter(new OutputStreamWriter(System
.out
));while(in
.nextToken()!=StreamTokenizer
.TT_EOF
){long a
=(long)in
.nval
;in
.nextToken();long b
=(long)in
.nval
;long q
=tgcd(a
,b
);if(1%q
!=0) {out
.println("sorry");}else {while(x
<=0){x
=b
;y
-=a
;}out
.println(x
" " y
);}out
.flush();} }static long tgcd(long a
,long b
){if(b
==0) {x
=1;y
=0;return a
;}long ans
=tgcd(b
,a
%b
);long team
=x
;x
=y
;y
=team
-a
/b
*y
;return ans
;}
}
總結(jié)
以上是生活随笔為你收集整理的杭电2669拓展欧几里得的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
