10104 - Euclid Problem

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10104 - Euclid Problem

Post by Hehe » Sun Dec 23, 2001 3:27 pm

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

Post by cyfra » Fri Mar 15, 2002 5:54 pm

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 :smile:

hburch
New poster
Posts: 3
Joined: Wed Apr 10, 2002 7:33 am

Post by hburch » Sun Apr 14, 2002 8:54 pm

cyfra wrote: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
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:

Post by Alexander Denisjuk » Mon Sep 23, 2002 10:28 am

hburch wrote:
cyfra wrote: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 :oops: 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

Post by htl » Sun May 11, 2003 4:34 pm

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:

Post by PMNOX » Sun Feb 08, 2004 2:55 pm

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

Post by wolf » Mon Sep 13, 2004 12:10 am

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

[cpp]
//AC
[/cpp]

Please, help me somebody...
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
Location: Bangladesh

Post by Noim » Sun Oct 17, 2004 9:52 pm

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

Post by wolf » Sat Oct 30, 2004 2:23 pm

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 :-D

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

10104 Need Help

Post by frankhuhu » Sun Feb 13, 2005 3:23 pm

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:

Post by frankhuhu » Tue Feb 15, 2005 3:16 pm

No one help me?? :cry:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 3:32 pm

Google for "extended Euclid"

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

10104 WA help

Post by vinay » Thu Apr 13, 2006 2:36 pm

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 :cry:
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:

Post by jan_holmes » Wed Apr 19, 2006 6:58 pm

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... :D

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

10104 - Euclid Problem

Post by taskin » Sun Jun 18, 2006 10:27 pm

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?

Post Reply

Return to “Volume 101 (10100-10199)”