UVa - 11827 ( Maximum GCD Solution )

Try Yourself First. For help Scroll Down .

Tip : To solve the problem you have to take the input as a string and store all the numbers in an array . And then find out the GCD of all possible pairs . After that find the maximum one. The problem you will face to solve the problem is to store numbers from the array. To find all the numbers you can use  " stringstream " as I used in my code. The process won't get TLE . I guaranty it. At the same way I got Accepted verdict at 0.00s . Go to code . One more thing use Euclidean Theorem to find GCD and obviously a Recursive Function . That will save much time.

Code :

#include<bits/stdc++.h>

using namespace std;

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


int main()
{
    int t,arr[1050];
    scanf("%d",&t);
    getchar();
    string s;
    while(t--)
    {
        getline(cin,s);
        stringstream ss(s); //stringstream used.
        int j=0;
        while(ss>>arr[j])
               ++j;
        int gcd=0;
        for(int i=0; i<j; i++)
        {
            for(int l=i+1; l<j; l++)
            {
                gcd = max(gcd ,callgcd(arr[i], arr[l]));

            }
        }
        printf("%d\n",gcd);
    }
    return 0;
}


=> Need Help . Leave a Comment .