BOJ 공약수 - 2436

2436번: 공약수

초등학생 수준의 수학으로 해결할 수 있는 문제다.(유클리드 호제법 제외)
최소공배수를 L, 최대공약수를 G라고 하자.

초등학생 때 저런식으로 G와 L을 구했던 기억이 있을것이다.
A와 B를 나눌 수 있을 때까지 계속 나누고 나눈 수들의 곱을 G라고 하고
G x a x b = L 로 구할 수 있었다.
G로 나누면, L / G = a x b 이 된다.
또한, A와 B를 나눌 수 없을때까지 나누고 남은 수가 a와 b이므로
a와 b는 서로소다.

이제 문제로 넘어가서 입력값에 L와 G가 주어지므로 L/G를 1부터 나눠보며 a, b를 구한다.
그리고 수의 차이가 최소며 서로소인 두 수를 구하면 된다.
또는 두 수의 최대공약수가 1이어도 서로소이다.

마지막으로 a, b에 G를 곱하면 A, B가 된다.

시간안에 해결될까? 시간복잡도를 계산해보자.

먼저 어떤 수 N을 1부터 나눈다고 해보자.
Trial Division 소수 판정법처럼 sqrt(N)까지만 나눠보면 된다.
때문에 a를 1부터 sqrt(L/G)까지만 나눠서 a와 b를 찾으면 시간이 줄어든다.

a와 b의 서로소 계산을 위해서는 2부터 sqrt(min(a, b)) 까지 나눠서
a와 b가 모두 나눠지는 경우가 있는지 확인한다. ( O(sqrt(min(a, b)) 의 시간복잡도를 가진다.)
or
gcd 알고리즘을 통해 최대공약수가 1인지 체크한다. ( O(log(a+b))의 시간복잡도를 가진다. )

첫번째 방법의 시간복잡도는 O(sqrt(N) * sqrt(min(a, b)) 이고,
두번째 방법의 시간복잡도는 O(sqrt(N) * log(a+b)) 이다.

문제에서 N이 가장 커질 때는 G=2, L=1억 일때다.
그럼 G/L = 5천만 이 되고, min(a, b)는 대충 최대값 잡아서
a=sqrt(5천만), b=sqrt(5천만) 으로 하자.
때문에 다음을 계산하면 된다.

첫번째 방법 계산

두번째 방법 계산

대충 60만, 10만므로 시간안에 '충분히' 해결된다.
또한 1부터 sqrt(N)으로 갈수록 a, b의 차이는 작아진다.

코드
두번째 방법이 속도면에서나 코드길이 면에서나 이득이 커보인다.

첫번째 방법

#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;
        }
    }

두번째 방법

#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;
}