BOJ Common Divisors - 2436

2436: Common Divisors

It's a problem you can solve with elementary-school math.(except the Euclidean algorithm)
Let the least common multiple be L and the greatest common divisor be G.

You probably remember finding G and L like that in elementary school.
You keep dividing A and B as long as you can, call the product of the divisors G,
and you could get it with G x a x b = L.
Dividing by G gives L / G = a x b.
Also, since a and b are what's left after dividing A and B until you can't anymore,
a and b are coprime.

Now on to the problem: L and G are given as input, so try dividing L/G starting from 1 to find a, b.
Then find the two numbers that are coprime with the smallest difference.
Alternatively, if the GCD of the two numbers is 1, they're also coprime.

Finally, multiplying a, b by G gives A, B.

Will it run in time? Let's calculate the time complexity.

First, say we divide some number N starting from 1.
Like the Trial Division primality test, you only need to divide up to sqrt(N).
So if you find a and b by dividing a only from 1 to sqrt(L/G), it takes less time.

To check whether a and b are coprime, divide from 2 to sqrt(min(a, b))
and check if there's any case where both a and b are divisible. ( It has a time complexity of O(sqrt(min(a, b)). )
or
Check whether the GCD is 1 using the gcd algorithm. ( It has a time complexity of O(log(a+b)). )

The time complexity of the first method is O(sqrt(N) * sqrt(min(a, b)),
and the time complexity of the second method is O(sqrt(N) * log(a+b)).

In this problem, N is largest when G=2, L=100 million.
Then G/L = 50 million, and for min(a, b), taking a rough maximum,
let's say a=sqrt(50 million), b=sqrt(50 million).
So we just need to calculate the following.

First method calculation

Second method calculation

Roughly 600k and 100k, so it's solved 'comfortably' in time.
Also, the closer you get from 1 to sqrt(N), the smaller the difference between a and b.

Code
The second method looks like a big win both in speed and in code length.

First method

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int G, L;

bool isDisjoint(int a, int b) {
    for (int k=2; k<=sqrt(min(a, b)); k++)
        if (a%k == 0 && b%k == 0)
            return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> G >> L;
    int T = L/G;
    for (int a=sqrt(T); a>=1; a--) if (T%a == 0) {
        int b = T/a, disjoint = true;
        if (isDisjoint(a, b)) {
            cout << a*G << ' ' << b*G;
            break;
        }
    }

Second method

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

int G, L, T, A, B;

int gcd(int a, int b) {return b==0?a:gcd(b, a%b);}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> G >> L; T = L/G;
    for (int a=1,b=T/a; a*a<=T; a++,b=T/a)
        if (T%a==0 && gcd(b, a)==1)
            A = a*G, B = b*G;
    cout << A << ' ' << B;
}