10104 - Euclid Problem

[Hehe]

What's wrong with this program?
Can any one help me?

[pascal]program u10104;
var
a,b,a0,b0,d,e,f,q,r,x,y,x1,x2,y1,y2:longint;
begin
while not eof do begin
readln(a,b);
a0:=a; b0:=b;
{a*x+b*y=d, d=gcd(a,n)=1}
x2:=1; x1:=0; y2:=0; y1:=1;
while b>0 do begin
q:=a div b;
r:=a-q*b;
x:=x2-q*x1;
y:=y2-q*y1;

a:=b; b:=r;
x2:=x1; x1:=x;
y2:=y1; y1:=y;
end;
d:=a; x:=x2; y:=y2;

if (x>0) and (b0>0) then begin
e:=a0 div d;
f:=b0 div d;
q:=1+(x-1) div f;
x:=x-q*f;
y:=y+q*e;
end;
writeln(x:1,' ',y:1,' ',d:1);
end;
end.
{@end_of_source_code}[/pascal]

[Edited by fpnc in order to test Pascal color syntaxis]

[cyfra]

Hi!
Your program gives wrong answers...

Here is the example:
1 3

My program 1 0 1
Your program -2 1 1
it is correct, but don't forget about this:

X<=Y and |X|+|Y| is the minimal.

I hope it will help
Good Luck

[hburch]

Here is the example: 1 3

My program 1 0 1
Your program -2 1 1
it is correct, but don't forget about this:

X<=Y and |X|+|Y| is the minimal.

Since 1 > 0 (X>Y), I think "1 0 1" is illegal output.

"-2 1 1" seems right to me (but I'm getting WA on it right now).

[Alexander Denisjuk]

Here is the example: 1 3

My program 1 0 1
Your program -2 1 1
it is correct, but don't forget about this:

X<=Y and |X|+|Y| is the minimal.

Since 1 > 0 (X>Y), I think "1 0 1" is illegal output.

"-2 1 1" seems right to me (but I'm getting WA on it right now).

I ment that (|X|+|Y| is the minimal) is primary criterium and (X<=Y) is secondary one. Sorry for an ambiguousity Thanks for remark. I tried to fix the problem description.

[htl]

The statement of the prob confuses me. It says "If there are several such X and Y, you should output that pair for which |X|+|Y| is the minimal (primarily) and X<=Y (secondarily)." Can someone give me some examples??

Here's my code:
[c]
#include<stdio.h>
long x,y,d;
void extended_euclid(long,long);
long divide(long,long);
void main(void)
{
int swap;
long a,b,t1,t2,t;
while(scanf("%ld %ld",&a,&b)!=EOF)
{
if(a==b)
{
printf("0 1 %ld\n",a);
continue;
}
extended_euclid(a,b);
a/=d,b/=d;
t1=divide(x+y,a-b),t2=divide(y-x,a+b);
if(t1<=t2)
t=t1;
else
t=t1-1;
x=x+b*t,y=y-a*t;
printf("%ld %ld %ld\n",x,y,d);
}
}
void extended_euclid(long a,long b)
{
long t;
if(b==0)
d=a,x=1,y=0;
else
{
extended_euclid(b,a%b);
t=x;
x=y,y=t-a/b*y;
}
}
long divide(long a,long b)
{
if(a==0)
return 0;
if(a<0 && b<0)
return (-a)/(-b);
if(a>0 && b>0)
return a/b;
if(a<0)
return (-a)/b-1;
if(b<0)
return a/(-b)-1;
}
[/c]

[PMNOX]

it means that abs(x) + abs(y) has to be as low as possible
if you have pairs:
(-1) (3) the sum is 4

(1) (-2) the sum is 3

that's why you choose second pair instead of first one.
If you have two pairs with equal sum then you take player in which x < y

[wolf]

What's wrong with my simple code. It works for any input I have.

[cpp]
//AC
[/cpp]

Please, help me somebody...

[Noim]

check this input and output:

5 9
1 10
0 0

2 -1 1
1 0 1

i think these case you just swap x and y. but doing these, does the given equation ax+by=d satisfY?

[wolf]

Thanx a lot Noim ! I got AC now. It was a month ago I posted this code, I thought nobody reply, and now ... Thx again

[frankhuhu]

This problem is not a hard one ,I think.But it confuse me a lot.I use a loop for(y=-b;y<=b;y++) to find the suitable x and y.But TLE.So I wonder is there a formula that can find the x,y quickly.Please help me !!!Thx

[frankhuhu]

No one help me??

[little joey]

Google for "extended Euclid"

[vinay]

can someb'dy give test cases..
I m getting WA.

I think i should paste my code.
it is based on extended euclid algorithm..

#include<iostream>

using namespace std;

int main(){
long long m, n, x, y,lastx,lasty,temp,tt,q;
while(cin>>m>>n){
/* if(m==0 || n==0){
cout<<"0 0 0\n";
continue;
} */
if(m<n){
long long tt=m;
m=n;
n=tt;
}
x=0;
y=1;
lastx=1;
lasty=0;
while(n!=0){
temp=n;
q=m/n;
n=m% n;
m=temp;

temp=x;
x=lastx-q*x;
lastx=temp;

temp=y;
y=lasty-q*y;
lasty=temp;

}
if(lastx>lasty){
temp=lastx;
lastx=lasty;
lasty=temp;
}
cout<<lastx<<" "<<lasty<<" "<<m<<endl;
}
return 0;
}

please help...
its frustrating

[jan_holmes]

input :
0 5
89 56
89 446
1555 169777
150 3005

output :
0 1 5
17 -27 1
-5 1 1
-21072 193 1
-20 1 5

Hope it helps...

[taskin]

If there are several such X and Y, you should output that pair for which |X|+|Y| is the minimal (primarily) and X<=Y (secondarily).

how can i test this? i use following algorithm--
Extended(a,b)
if b = 0 then return (a,1,0)
(d1, x1, y1) <--- Extended (b, a mod b)
(d, x, y) <---- (d1, y1, x1 - floor(a / b) * y1)
return (d, x, y)

this pass all the inputs of previous posts, but i think this algorithm does not check the above condition. how can i include the required condition in this algorithm?