## 10104 - Euclid Problem

Moderator: Board moderators

Hehe
New poster
Posts: 2
Joined: Tue Dec 18, 2001 2:00 am

### 10104 - Euclid Problem

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
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

Here is the example:
1 3

My program 1 0 1

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

I hope it will help
Good Luck hburch
New poster
Posts: 3
Joined: Wed Apr 10, 2002 7:33 am
cyfra wrote:Here is the example: 1 3

My program 1 0 1

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
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
hburch wrote:
cyfra wrote:Here is the example: 1 3

My program 1 0 1

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
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10104

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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
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
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

### 10104 - "Euclid problem" WA

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

[cpp]
//AC
[/cpp]

Last edited by wolf on Sat Oct 30, 2004 2:24 pm, edited 1 time in total.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
check this input and output:
input wrote: 5 9
1 10
0 0
output wrote: 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?
__nOi.m....

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
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
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

### 10104 Need Help

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
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:
No one help me?? little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### 10104 WA help

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;
}

its frustrating If I will myself do hashing, then who will do coding !!!

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
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... New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm