11827 - Maximum GCD

[KAI10]

Hello, i,m getting runtime error for this code. can any body point out the bug please. really need help .....

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}

[brianfry713]

Your code is throwing a divide by 0 (b = 0) on line 6 running the sample input:
if (a%b==0) return b;

[KAI10]

thanks, i got rid of RE. But now i am getting WA . please help........

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long GCD(long long a,long long b)
{
    if (!b) return a;
    if (!a) return b;
    if (a%b==0) return b;
    return GCD(b,a%b);
}

int main()
{
    int T,p;
    scanf("%d", &T);
    T++;
    for (p=0; p<T ;p++){
        char ch,str[1000];
        long long M[105],count=0,j,l,num=0,i,max=0,k;
        gets(str);
        for (i=0;; i++){
            char str1[1000];
            if (str[i]==' ' || str[i]=='\0'){
                l=0;
                for (j=count; j<i; j++) {str1[l] = str[j]; l++;}
                str1[l]='\0';
                M[num] = atoi(str1);
                num++;
                count = i+1;
            }
            if (str[i]=='\0') break;
        }
        for (j=0; j<num; j++){
            for (k=j+1; k<num; k++){
                l = GCD(M[j], M[k]);
                if (l>max) max = l;
            }
        }
        if (p) printf("%lld\n", max);
    }
    return 0;
}

[brianfry713]

Doesn't match the sample I/O.

[uDebug]

Here's some input / output that I found useful during testing / debugging.

Note that the judge's input does not have a case like the 4th one below but I think it makes sense to handle this, so, I threw it in.

Input:

Code: Select all

4
     45      20     30        40 100          10000        1500
  13                20                    93     31         
     0   99          
              0                         

AC Output:

Code: Select all

500
31
99
0

[LazyTym]

Why getting WA?????????????i think it's an easy problem bt i can not find the bug...........pls help.......

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;

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

int main()
{
    int A[101];
    int t,a;
    cin>>t;
    while(t--) {
        int i=0,c;
        int p,maximum=0;
        char ch;
        do
        {
            scanf("%d%c",&A[i],&ch);
            i++;
        }
        while(ch==' ');
        c=i--;

        for(int i=0;i<c-1;i++) {
            for(int j=i+1;j<c;j++) {
                if(A[i]<A[j]) {
                   p=EUCILD(A[j],A[i]);
                }
                else {
                   p=EUCILD(A[i],A[j]);
                }
                if(maximum<p) maximum=p;
            }
        }
        cout<<maximum<<endl;
    }
    return 0;
}

[brianfry713]

Your code doesn't work on the sample input. Try parsing the input line by line and then use something like strtok or stringstream to extract the tokens of each line.

[richatibrewal]

Hii,the following code got accepted for 0.015 s. How can I improve this code ?

Code: Select all

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    int r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int n,a[200]={0},i,j,max=-1,l,len,flag,g;
    char s[100096];
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        j=-1;
        max=-1;
        flag=1;
        fgets(s,100096,stdin);
        for(i=0;i<=strlen(s)-1;i++)
        {
            if(s[i]==' ')
            {
                flag=1;
                continue;
            }
            if((flag==1)||(i==strlen(s)-1))
            {
                a[++j]=0;
                flag=0;
                for(len=j-2;len>=0;len--)
                {
                    g=gcd(a[j-1],a[len]);
                    if(g>max)
                        max=g;
                }
            }
            if(i<strlen(s)-1)
            {
                l=s[i]-48;
                a[j]=(10*a[j])+l;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}