10104  Euclid Problem
Moderator: Board moderators
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
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:=aq*b;
x:=x2q*x1;
y:=y2q*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+(x1) div f;
x:=xq*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]
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:=aq*b;
x:=x2q*x1;
y:=y2q*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+(x1) div f;
x:=xq*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]

 New poster
 Posts: 35
 Joined: Sat Jan 05, 2002 2:00 am
 Contact:
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.hburch wrote:Since 1 > 0 (X>Y), I think "1 0 1" is illegal output.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.
"2 1 1" seems right to me (but I'm getting WA on it right now).
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,ab),t2=divide(yx,a+b);
if(t1<=t2)
t=t1;
else
t=t11;
x=x+b*t,y=ya*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=ta/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)/b1;
if(b<0)
return a/(b)1;
}
[/c]
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,ab),t2=divide(yx,a+b);
if(t1<=t2)
t=t1;
else
t=t11;
x=x+b*t,y=ya*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=ta/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)/b1;
if(b<0)
return a/(b)1;
}
[/c]
10104  "Euclid problem" WA
What's wrong with my simple code. It works for any input I have.
[cpp]
//AC
[/cpp]
Please, help me somebody...
[cpp]
//AC
[/cpp]
Please, help me somebody...
Last edited by wolf on Sat Oct 30, 2004 2:24 pm, edited 1 time in total.
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
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=lastxq*x;
lastx=temp;
temp=y;
y=lastyq*y;
lasty=temp;
}
if(lastx>lasty){
temp=lastx;
lastx=lasty;
lasty=temp;
}
cout<<lastx<<" "<<lasty<<" "<<m<<endl;
}
return 0;
}
please help...
its frustrating
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=lastxq*x;
lastx=temp;
temp=y;
y=lastyq*y;
lasty=temp;
}
if(lastx>lasty){
temp=lastx;
lastx=lasty;
lasty=temp;
}
cout<<lastx<<" "<<lasty<<" "<<m<<endl;
}
return 0;
}
please help...
its frustrating
If I will myself do hashing, then who will do coding !!!

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
10104  Euclid Problem
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?
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?