## 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

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:
TIME LIMIT EXCEEDED. WHY?

Code: Select all

#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int gcd (int p,int q)       //gcd function running fine
{
int t;
if (p==0 || q==0)
{if (p==0)
return q;
else
return p;
}
if (q>p)
{t=p;
p=q;
q=t;
}
while (q>0)
{
t=q;
q=p%q;
p=t;
}
return p;
}

int main()
{
int a,b;
while (cin>>a>>b)
{
int d,x,y=1,m,n;
bool flag=true,flag1,f=false;
d=gcd(a,b);
if(a!=0 && b!=0)
flag1=true;
if(a==0 && b==0)
f=true;
if(f!=true){
while (flag==true)
{if(a!=0 && b!=0)
{
if (((d-b*y)%a)==0)
{x=((d-b*y)/a);
flag=false;
}
y++;
}
else
{x=0;
y=2;
flag=false;
}
}
int x1,y1=-1;

while (flag1==true)
{
if (((d-b*y1)%a)==0)
{x1=((d-b*y1)/a);
flag1=false;
}
y1--;
}

if(abs(x)+abs(y)<=abs(x1)+abs(y1))
cout<<x<<" "<<y-1<<" "<<d<<endl;
else
cout<<x1<<" "<<y1+1<<" "<<d<<endl;
}
else
cout<<"0"<<" "<<"0"<<" "<<"0"<<endl;
}
return 0;
}

[b][/b][b][/b]
win

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Salamo Aleko
This is a known algorithm, i used it as it is....
Its recursive calls will do every thing...Just print ....No compare, no check just ouput...HMHMHM
Sleep enough after death, it is the time to work.

New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
yes, nothing additional is needed after this algorithm. but i made a small mistake in my implementation after rechecking & now its AC.

New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
correction of previous post :
"but i made a small mistake in my implementation & after rechecking now its AC."
im in sleepy mind.

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am
jan_holmes wrote:
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...
Second requirement in the problem is "X <= Y"
But the 3rd output violates that....

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

### Re: 10104 - Euclid Problem

Code: Select all

Removed after ACC
I'm getting TLE. I thought it might be because of the iterative form of Euclid's algorithm, but it shouldn't be any slower than the recursive form. Does this problem have a really large input that isn't kind to Java users?
Last edited by wjomlex on Fri Dec 19, 2008 8:44 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10104 - Euclid Problem

java.util.Scanner is generally a very slow class.
Try to replace with StringTokenizer and BufferedReader.

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

### Re: 10104 - Euclid Problem

I know that Scanner's slow, but somehow I doubt that it's the bottleneck in this problem. Usually Scanner is only an issue in problems that have a lot of input per case, like graph or map problems. But, I'll give it a shot ^_^

I wish I didnt' have to though. In any real contest, Scanner works just fine... UVa should allot extra time for Java like PKU's judge.

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

### Re: 10104 - Euclid Problem

What do you know? It works with BufferedReader in 2.870s. That's really pushing it.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 10104 - Euclid Problem

IT is one of the easiest problem in UVA
Nothing is minimal or ordered here

Just take input
and
run extended_euclid algorithm

print the triples

ok

i think u will get accepted now
Try to catch fish rather than asking for some fishes.

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10104 - Euclid Problem

what would be the output for

0 0?

would it be nothing or a blank line?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10104 - Euclid Problem

amishera wrote:what would be the output for

0 0?

would it be nothing or a blank line?
My AC code prints

1 0 0

But I doubt that there is an input like that..

asif3058
New poster
Posts: 1
Joined: Tue Mar 05, 2013 8:02 am

### Re: 10104 - Euclid Problem

#include<stdio.h>
#include<iostream>

using namespace std;

int gcd(int a,int b,int &x,int &y)
{
if(a==0)
{
x=0;
y=1;
return b;
}
int x1,y1;
int d=gcd(b%a,a,x1,y1);
x=y1-(b/a)*x1;
y=x1;
return d;
}

int main()
{
// freopen("in.txt","r",stdin);

int a,b;

while(scanf("%d %d",&a,&b)!=EOF)
{
int x,y,d;
d=gcd(a,b,x,y);

printf("%d %d %d\n",x,y,d);

}
}

why WA? here i use extended euclid method.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10104 - Euclid Problem

It looks like you figured it out
Check input and AC output for thousands of problems on uDebug!

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm