GCD2

I swear I solve it correctly, but it says my answer is wrong! :(

Well, the test cases are proper. You might want to check your algorithm by checking it against smaller values, the answer to which you can find either manually or by bruteforce.

No, the solution to this problem is far simpler than that.

@Rajarshi You don't need fast fourier transforms to solve this problem :)

What is the name of the input file ?

You have to read input from standard input (stdin) and the output should be written to standard output (stdout)

Can anyone point me to a place that explains how to handle large numbers in C without arrays? I found some algorithms that will do this, but how do you handle an integer with 10^250 digits? Do you make a type in C or something? If someone can point some place where I can do some research, I would appreciate it.

You would need an array to do that.

actually i submitted the solution,it shows solution is too long max limit is 1000bytes or sometimes it shows runtime error.i tested for both large n small inputs,workn fine.

size of solution is actually around 750bytes.

You are getting a segmentation fault. You are accessing some array value which you aren't supposed to.

oh...is there any limit for number of lines of input...? in problem not specified...also for code size is ther any limit....

i got it...!!

oooooh..

i have solved it correctly..taken care of everything still can;t get it!!!! where i m wrong!@   !!!!!help needed...

The range of A is 0<=A<=40000 , how can one find  the GCD of zero and a number

The same way you find the GCD of anything else. It is the largest number which divides evenly into both. Nothing special about 0.

can't i solve this using Java...because when i submit the solution,its says you cant sue this language for this problem solution,but in the languages JAR  is allowed??

I also would like to know why Java is not allowed. JAR is allowed but the source limit 1000 makes it impossible to use.

BTW there is something odd with the timestamps you are using for comments. I wrote the previous comment after 'Ajay Patel's comment but from the times of the comments it looks like I wrote it 4 hours before him.

The timestamp issue will be fixed.

do we consider for case where any of the num is 0 ???

Yes

i implemented all the library functions that i needed , myself ...code runs for 250 lines

it is giving correct results , i  cross checked many times... but the size of the code exceeds 1000 bytes :(

is it better to use library functions ??? , does the included code (in case of a c program) contribute to the size of the code as well ???

This problem can be solved without using any library functions.

Could you, please, tell me why JAVA is not allowed for this problem? Is it a bug or is it intentional? If it is a bug then, please, fix it. If it is intentional, please, give me some justification. Note that JAR is allowed but the source limit 1000 makes it impossible to use.

I presume the reason it is not allowed is because the problem is intended to be solved without big integer calculations, and a solution with BigInteger in Java would be trivial.

+1 at Stephen

@Stephen and @Codechef: I don't believe this explanation ;-). It doesn't explain why other languages like JAR and NICE are allowed. I just had to change the syntax of my JAVA program to fit the syntax of NICE. Moreover, it is quite easy to avoid BigInteger in this case, but it is very difficult in INSOMB1 (Primality Testing) problem where JAVA is allowed. Hence, there is some inconsistency, at least.

what's the output for case : a=0, b=0 ????

http://en.wikipedia.org/wiki/Greatest_common_divisor

Greatest Common Divisor is defined only for non zero integers. And I don't understand as to how you define the greatest common divisor for 0 and 0.

There won't be a test like 0 0

WHY ARENT THEY ALLOWING JAVA IN THIS PROBLEM?

JUST FOR THE BIGINTEGER'S SAKE, I DOUBT.

MY EFFECTIVE CODE IS JUST 23 LINES AND WORKS PERFECT.

@Karan: Yes, it is silly that Java is not allowed for this problem. The simplest solution for us, Java programmers, is to port your solution to NICE. It has almost the same syntax. Just remove the class stuff (e.g. leave just methods). Replace imports like java.math.BigInteger by java.math.* and remove public/private/protected keywords. You should end up with a valid NICE program that is allowed in GCD2.

i solved this problem in python but after submitting i got the message that i can not submit this problem in python. why????

is this workable in ADA??

wen i try to submit soln it shows this error

The requested URL is not supported

The requested URL is not supported

[%S]

whats this?????

plz rply

is there a new line at the end of input??

@Jan: I guess JAR isn't impossible to use after all :^)

The naive solution is very slow, however.

some advantages of jarfiles: they're compressed, you can name sources whatever you like (doesn't have to be Main.java), multiple sources and multiple data files are possible; and, if you're interested in keeping your algorithm a secret, it's not easy for people to read, though theoretically possible with a decompiler.

My code seems to work ok. But i always get wrong answer here.I do not understand what is happening.And Stephen Merriman got a point about BigInteger class.

You don't handle A=0 properly, for one.

Thank you. I suppose gcd(0,x) where x>=40000 suppose to give x. I must have forgetten the fact that atoi has a limit,of course:D

I did what Mr.Merriman suggested. It works perfectly for me but not for the judge. I still do not see what's wrong. Sorry for keeping this comment wall busy.

#include<stdio.h>

int gcd(int,int);

int main()

{

int a,b,g[10],n,i;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d%d",&a,&b);

g[i]=gcd(a,b);

}

for(i=0;i<n;i++)

{

printf("%dn",g[i]);

}

return 0;

}

int gcd(int a,int b)

{

if(a<b)

return gcd(b,a);

else if(b==0)

return a;

else

return gcd(b,a%b);

}

^ In case you are asking for a problem in your program. I'd recommend reading the input constraints again.

@Antarpreet Singh

should I give input into a file and then proceed?

No, you are supposed to read from standard input and standard output like your program tries to do.

then whats wrong with my code?

plz tell me, I'm new to codechef

You have lots of things wrong. For example, where does it say in the problem that there are less than 10 test cases? And have you looked at how big B can be?

i am geting runtime error , anyhints y these occur ?? The program runs fine for large nums(tested within range of long int) and multiple test cases in my computer , its also working(cant check answer) for num > 10^100 ..

shouldnt more apt response be wrong answer than runtime error ??

i am luving the corner cases ...

but time limit exceeded , what is more faster input method than getchar() ?? , i dont have any computationaly intensive job in the program

@ gunjan

i dont think we need much faster input method to solve in time limit... i used simply scanf to take A as  input and cin for B and it works fine with accepted time 0.00  sec

i agree with devendra. though i used scanf for both A and B. (i used c)

i am still getting TLE , my algo is O(Number of digits in B) . Number of flops is about 7*numdigits + of gcd(small_num,num<small_num) any ideas y ? do we need a much better algo ??

i am sorry , i had a grossly wrong algo realised my mistake :)

I have tried my code for about a 240 digits long B and its giving the right answer. I think I'm mistaking somewhere in representing my answer. My code is here http://www.codechef.com/viewsolution/246536.

Why doesnt minimum memory go below 1.6mb ?? I tried my best it is still stuck at 1.6mb . Same code runs in about 2.5mb in g++ compiler . Does codechef attaches some sort of debugger ?? were can i get more on this ??

hey , plz some 1 help ....

how could we take a number as an input whose number of digit is 10^250 in C programming.....

The language is unclear: "and it proposes to Frank that makes it but with".

@Jan Stola

I know it's not right to paste code out here, but after making correctly in java, i'm really curious to convert my code to NICE, but i still keep getting errors

JAVA CODE:-

import java.io.*;
import java.util.*;
import java.math.*;
void main(String[] args)throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

int n=Integer.parseInt(br.readLine());
String[] in=new String[1000];

for(int i=0;i<n;i++)
in[i]=br.readLine();

for(int i=0;i<n;i++){
StringTokenizer st=new StringTokenizer(in[i]);
BigInteger one=new BigInteger(st.nextToken());
BigInteger two=new BigInteger(st.nextToken());
System.out.println(one.gcd(two));
}

}

Error:-

C:Nicemainmain.nice: line 10, column 10:
Incorrect type in assignment to in
Found   : ?java.lang.String[]
Expected: java.lang.String[]
compilation failed with 1 error

Please could u help me out with the possible correcytions in the java code, i really want to complete this problem :)

What i could possible convert by your comment:-

import java.io.*;
import java.util.*;
import java.math.*;
class Main{
public static void main(String[] args)throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

int n=Integer.parseInt(br.readLine());
String in[]=new String[1000];

for(int i=0;i<n;i++)
in[i]=br.readLine();

for(int i=0;i<n;i++){
StringTokenizer st=new StringTokenizer(in[i]);
BigInteger one=new BigInteger(st.nextToken());
BigInteger two=new BigInteger(st.nextToken());
System.out.println(one.gcd(two));
}

}}

CORRECTION:- Oops, in the Previous comment, the JAVA code is actually the NICE code :)

[code]#include<iostream>
using namespace std;

int gcd(int x,int y)
{if (y==0)return x;else return gcd(y,x%y);}
int gcdlarge(int a,char *b)
{
int val=0,i=0,y;
while(val<a)
{
val= val*10 + *(b+i)-'0';i++;
}
y=val%a;
while(*(b+i)!='')
{
y=(y*10+*(b+i)-'0')%a;i++;
}
return gcd(a,y);
}

int main()
{
int t,a,x,i;
char b[250];
cin>>t;
for(i=0;i<t;i++)
{
scanf("%d %s",&a,b);
x = gcdlarge(a,b);
cout<<x<<endl;
}
}
[/code]

I am getting runtime exception. Its working on my machine. Can anyone tell whats the problem??

One mistake is that the input could have 250 digits, and your code only works for up to 249 digits.

even making it 260 doesnt work??? i am getting runtime exception. can anyone suggest me a good input method..

I have tried using string class. getline method and much more but nothing seems to be running.. everytime i have a runtime exception

Another mistake is that you haven't read the input bounds carefully.. your code fails on a rather easy test case.

Can anyone give me some test cases. i am always getting a wrong answer. :(

M gettin a runtime error of type other i.e runtime(other)....can someone plz suggest me a solution of it.....asap.....m stuck to this prob...........

How 0 case should be handled? I am assuming there wont be any output for A=0. also checking boundary for A. but getting WA. Can anybody help with that? Admin, can u give some hints?

Ok assuming gcd(A,B)=gcd(0,B)=B, but still getting  wrong answer. What may be the trick?

You have a pretty basic mistake in one of your scanf statements.

How can we reduce the memory usage in a C program,(I always get a mem usage of 1.6M)?

can any plez suggest how 2 handle these huge inputs . please elaborate or atleast suggest some directions...

@admin

Why is the source code limit so less for this question? it's around 50000 for most problems but only 1000 for this one. I seem to have solved this question but my source code size is around 1700. What should I do?

Write a program with less code. It is deliberately set low to prevent some wrong methods passing.

A correct solution should easily fit within 1000 bytes.

Can someone please tell me why my code to this problem is wrong?

using System;
class Program
{
static int call_div(string str,int div)
{
int len=str.Length,temp=0;
for(int i=0;i<len;i++)
{
temp=temp*10+(str[i]-48);
temp%=div;
}
return temp;
}
static int gcd(int x,int y)
{
if(x==0)
return y;
else
return gcd(y%x,x);
}
static void Main(string[] args)
{
int loop=int.Parse(Console.ReadLine());
int numb;
while(loop-->0)
{
string[] Numbs=Console.ReadLine().Split(' ');
if (Numbs[0]=="0")
{
Console.WriteLine(Numbs[1]);
}
else if(Numbs[0]=="1")
{
Console.WriteLine("1");
}
else
{
numb = call_div(Numbs[1], int.Parse(Numbs[0]));
Console.WriteLine(gcd(int.Parse(Numbs[0]), numb));
}
}
}
}

can someone guide how to reduce size of this.

#include<iostream>
using namespace std;
int main()
{
int t;
int i,rem;
char string[251];
int num;
scanf("%d",&t);
while(t--)
{
scanf("%d",&num);
scanf("%s",&string); 
if(num!=0)
{    i=0;    rem=0;
while(1)
{                   if(string[i]=='')
break;                                                                       
rem=rem*10+(string[i]-'0');                                                             
rem=rem%num;
i++;                                 
}
if(rem!=0)
{
while(1)
{
i=num%rem;
if(i==0)
{
break;
}
num=rem;
rem=i;

}
}
else
rem=num;
printf("%dn",rem);
}
else
{
printf("%sn",string);
}
}

return 0;

}

i am getting runtime error but i am unable to find any mistake

pls admin can you have alook at my code

#include<stdio.h>
#include<string.h>
int main()
{
int divisor,number,remainder,len,l,test,array[251],i;
char extra[252];
scanf("%d",&test);
for(l=0;l<test;l++)
{
scanf("%d",&divisor);scanf("%s",extra);len=strlen(extra);
for(i=0;i<len;i++)array[i]=extra[i]-48;
int counter=0,flag=0;number=0;
while(1)
{
if(counter==len)
break;
while(number<divisor)
{

if(counter==len)
{
remainder=number;
flag=1;
break;
}
if(counter!=0)
number=number*10;
number=number+array[counter];
counter++;
}
if(flag==1)
break;
remainder=number-(number/divisor)*divisor;
number=remainder;
}
printf("%dn",gcd(divisor,remainder));

}

return 0;
}
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}

i m soory to post the code in comments section

anyway i got the mistake i was dividing by 0

Can you please provide any special case.. I am getting right output for above sample input and also for all of my entered inputs.. still getting wrong answer.. Please have a look at my code..http://www.codechef.com/viewsolution/408371

just ignore my comment.. the question had confused me.

Can you tell me what the exact runtime error is for this c# solution?

http://www.codechef.com/viewsolution/485812

I have tried installing Mono 2.01 (albeit, Windows) and throwing huge amounts of data at that solution but I can't break it. When I submit it fails with run time error (other).

Thanks

Hi Admin,

One thing I would like to say that the source limit constraint should not be so strict.

I wrote the program and the size of program was 1KB and this problem requires <= 1000 Bytes.

So, I just shortened the variable names which were otherwise readable and appropriate, for example I shortened 'length' to 'l'.

By the way, a good problem.

Umm seems like the server's down or something...  Nobody's problems are running at the moment..