BOJ 2824 최대공약수

출처: https://www.acmicpc.net/problem/2824

---

문제 설명

주어진 수들을 곱해서 만들어지는 큰 수 N, M 의 최대 공약수를 구하는 문제

---

입력

N을 만드는 곱할 수의 개수(n), 곱할 수들(n_1, ... , n_n) 열, M을 만드는 곱할 수의 개수(m), 곱할 수들 (m_1, ..., m_m)

출력

최대 공약수를 출력한다. 단, 최대 공약수가 1e9 보다 크다면 마지막 9자리만 출력한다. 

---

입력 예

3

2 3 5

2 

2 5

출력 예

10

제약조건

1 <= N, M <= 1000, 1 <= n_i, m_i <= 1e9

---

문제 풀이

곱해서 만들어지는 큰 수를  A, B 라고 할때,  prime factorization 을 하면, A = p1^a1 x p2^a2 ... B = p1^b1 x p2^b2 ... 형태로 쓸 수 있고, 같은 소수가 있을 때 그중 거듭제곱이 낮은 것들을 골라서 모두 곱하면 최대 공약수가 된다. 이것을 위해서 곱해서 만들어지는 수들을 각각 소인수분해를 하고 그것을 map<int, int>에 저장한다. 나중에 하나를 기준으로 작은 것들을 골라서 곱하고 크기가 1e9과 비교해서 더 커지지 않는지 확인해서 출력한다. Modulo 연산은 곱셈에 닫혀 있으므로 곱하는 중간에 처리해도 결과 값은 달라지지 않는다.

프로그램 내용

for(map<int, int>::iterator it = f_n.begin(); it != f_n.end(); ++it)
    {
        int prime;
        int power;
        
        prime = it->first;
        power = min(it->second, f_m[prime]);
        
        // cout << prime << " " << power << "\n";
        
        for(int i = 0; i<power; ++i)
        {
            ans *= prime;
            
            if(ans >= MAX_F)
            {
                ans %= MAX_F;
                flag = true;
            }
        }
    }

 

관련된 문제