BOJ 2824 최대공약수

BOJ 백준 2824 C++

최대공약수

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

 

 

아. 엄청 고생했던 문제.. 잊을 수 없다.

 

 

1) 약수 구하기의 응용문제, 주어지는 수가 매우 커서 오버플로우에 주의해야 한다.

2) 처음에는 배열 인덱스를 이용해서 약수의 개수를 카운트하려고 했는데, 약수 input의 값이 최대 999,999,999이기 때문에 배열 메모리 초과를 예상하고, map 자료구조를 이용해서 <key,value> -> <약수, 약수가 사용된 횟수> 를 만들었다.

3) 약수를 구할 때, 두 가지 방법을 이용했다

3-1) 약수의 특성을 이용해서 j*j까지 확인하기 (j*j<x아닌 j<x로 확인하면 시간 초과 발생)

3-2) 에라토스테네스의 체를 이용해서 prime[] 배열에 약수인지 미리 구해놓기.

각 A, B의 N,M의 input이 최대 999,999,999이므로 나올 수 있는 최대 약수는 대략 40,000이다 (40,000*40,000 = 1,600,000,000) -> 약수의 특성임

 

처음에는 3-1 방법을 구현했다가 자꾸 시간 초과 나서 3-2로도 구현해봤는데(결국 둘 다 구현) 

최종적으로 시간 비교해 보니 [ 3-1 : 28ms /  3-2 : 168ms ] 정도로 차이가 났다.

 

3) 여기서 내가 생각하지 못한 문제점 -- 1

그래서 약수로 나누어지는지 확인하는 과정에서, j가 40,000을 넘으면 더는 N(또는 M의) 약수가 없다고 판단하고 map에 그 자신을 insert 해야한다.

for문을 나왔을 때 x가 1이면, 더는 x의 약수가 존재하지 않고

x가 1이 아니라면 자신이 약수가 되어야 한다.

 

4) 또 다른 문제점 -- 2

약수를 모두 구한 후 ans( 두 수의 최대 공약수)를 만드는 과정에서 발생.

처음에는 pow()를 사용했는데, 크기가 작은 수의 연산일 때는 문제가 없었는데, ans의 값이 10자리 이상일 때 값이 정확히 나오지 않았다.

그래서 cnt만큼 for문 돌려서 해결했다.

 

5) 다음 문제점 -- 3

매우 큰 최대 공약수 ans를 계산하면서 이 값이 10자리 이상이면 (flag=true 체크), 9자리로 만들기 위해 %1,000,000,000을 해서 ans에 저장했다.

최종 출력 전, flag를 확인하여 출력한다. (flag=true : 한 번이라도 10자리 이상이 됐으므로 최종 출력은 '0'을 채워 9자리여야 함)

이 값이 123,456,789라면 그대로 출력하면 되지만.. 9자리로 만든 값이 123,456이면 앞에 0을 붙여 000,123,456으로 만들어야 한다.

stack을 사용해서 해결했다.

 

6) 생각지 못한 1번 문제점에서 시간을 엄청나게 보냈다..

 

7) 사용한 반례 -- 무조건 큰 수 넣어보는게 좋다

input	3 358572 83391967 82 3 50229961 1091444 8863	2 999999999 999999999 2 999999999 999999999	2 90000000 90000000 2 90000000 90000000
output	000012028	000000001	000000000

 

8) 그래도 해결이 안 된다면 https://ko.numberempire.com/numberfactorizer.php 에서 숫자 넣어서 소인수 분해된 값을 확인하여 map에 들어있는 값과 일치하는지 확인하자!

 

 

 

#1 -- 약수 구할 때 j*j 이용

 

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

int N, M;
map <int,int> mp1, mp2;
long long ans = 1;
bool flag=false;

void makeCnt(){
    int x;

    // A
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> x;

        for(int j=2; j*j<=x; j++){
            while(x%j==0){
                if(!mp1.empty()){
                    if(mp1.find(j) != mp1.end()) // mp1에 존재
                        mp1[j]++;
                    else  // mp1에 없음
                        mp1.insert();
                } 
                else mp1.insert(); // mp1에 없음

                x/=j;
            }
        }
        
        if(x!=1){
            if(mp1.find(x) != mp1.end()) // mp1에 존재
                mp1[x]++;
            else  // mp1에 없음
                mp1.insert();
        }
    }

    // B
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> x;

        for(int j=2; j*j<=x; j++){
            while(x%j==0){
                if(!mp2.empty()){
                    if(mp2.find(j) != mp2.end())
                        mp2[j]++;
                    else
                        mp2.insert();
                } 
                else mp2.insert();

                x/=j;
            }
        }
        
        if(x!=1){
            if(mp2.find(x) != mp2.end())
                mp2[x]++;
            else
                mp2.insert();
        } 
    }
}

void solve(){
    for(auto it=mp1.begin(); it!=mp1.end(); it++){
        long long val = it->first;

        if(mp2.find(val) != mp2.end()){
            int cnt = min(mp1[val], mp2[val]);
            
            for(int i=0; i<cnt; i++){
                ans *= val;
                if(ans>999999999) {
                    flag = true;
                    ans %= 1000000000;
                }
            }
        }
    }
}

void printNum(){
    string s = to_string(ans);

    if(flag){
        stack <char> st;

        for(int i=s.length()-1; i>=0; i--){
            st.push(s[i]);
        }
        while(st.size()<9){
            st.push('0');
        }
        for(int i=0; i<9; i++){
            cout << st.top();
            st.pop();
        }
    }
    else
        cout << ans;
}

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

    makeCnt();
    solve();
    printNum();

    return 0;
}

 

 

 

#2 미리 소수 구해 놓고 확인하기

 

bool prime[40000];
void wantPrime(){
    memset(prime, true, sizeof(prime));
    for(int i=2; i<40000; i++){
        if(!prime[i]) continue;
        for(int j=i+i; j<40000; j+=i)
            prime[j]=false;
    }
}

void makeCnt(){
    int x;

    // A
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> x;

        for(int j=2; j<40000; j++){
            while( prime[j] && x%j==0 ){
                if(!mp1.empty()){
                    if(mp1.find(j) != mp1.end()) // mp1에 존재
                        mp1[j]++;
                    else  // mp1에 없음
                        mp1.insert();
                } 
                else mp1.insert(); // mp1에 없음

                x/=j;
            }
        }

        if(x!=1){
            if(mp1.find(x) != mp1.end()) // mp1에 존재
                mp1[x]++;
            else  // mp1에 없음
                mp1.insert();
        }
    }

    // B
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> x;

        for(int j=2; j<40000; j++){
            while( prime[j] && x%j==0 ){
                if(!mp2.empty()){
                    if(mp2.find(j) != mp2.end())
                        mp2[j]++;
                    else
                        mp2.insert();
                } 
                else mp2.insert(); 

                x/=j;
            }
        }

        if(x!=1){
            if(mp2.find(x) != mp2.end())
                mp2[x]++;
            else
                mp2.insert();
        } 
    }
}