APPLEORANGE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Computing GCD quickly

PROBLEM:

Find the maximum number of people who can split N apples and M oranges equally.

EXPLANATION:

Suppose there were k people. Then, for equal distribution, k must be a divisor of N and a divisor of M.

The largest such k is, by definition, \gcd(N, M); and this is the answer.

Finally, since N and M can be quite large, it’s necessary to compute \gcd(N, M) quickly. This can be done with the help of the Euclidean algorithm, or you can just use inbuilt functions corresponding to your language (std::gcd in C++, math.gcd in Python, and so on).

TIME COMPLEXITY:

\mathcal{O}(\log\min(a, b)) per testcase.

CODE:

Code (Python) 
from math import gcd
for _ in range(int(input())):
    n, m = map(int, input().split())
    print(gcd(n, m))
2 
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stdio.h>
using namespace std;

int main()
{
    int testC;
    cin>>testC;
    while(testC--)
    {
        int n, m;
        cin>>n>>m;
        int mn, mx;
        for(int i=1;i<1000;i++){
            if(n%i==0 && m%i==0){
                mx=max(mx,i);
            }
        }
        cout<<mx<<endl;
    }
}

I know that gcd is better to find this solution, but why the above method is wrong?

1 Like
3

Because it has greater time complexity than the gcd method

1 Like
4

GCD is the only correct answer.

For example, if N = M = 10^9, the answer is 10^9. Iterating till 1000 isn’t enough.

1 Like
5

Okay. Thanks.

6

Okay got it. Thanks :slightly_smiling_face::+1:t2:.