44 条题解
-
0flycode LV 7 @ 2013-04-30 10:06:36
扩展欧几里德算法
var
x,y,a,b,d:int64;
procedure gcd(a,b:int64);
var
t:int64;
begin
if (a mod b = 0) then
begin
x:=0;
y:=1;
end
else
begin
gcd(b,a mod b);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
begin
readln(a,b);
d:=b;
gcd(a,b);
writeln((x mod d+d) mod d);
end. -
02013-03-16 09:30:36@
刚看了一个小时扩展欧几里得。。。
-
02012-11-20 17:39:02@
sofa
-
-12017-08-04 08:06:21@
Enjoy.
#include<cstdio> #define LL long long using namespace std; LL A,B,X,Y; LL ExGcd (LL a,LL b,LL &x,LL &y) { if (!b) {x=1,y=0;return a;} int as=ExGcd(b,a%b,x,y); int t=x;x=y;y=t-(a/b)*y; return as; } int main () { scanf("%lld%lld",&A,&B); LL gcd=ExGcd(A,B,X,Y),lcm=A*B/gcd; while(X<0) {X+=lcm/A;Y-=lcm/B;} printf("%lld",X); return 0; }