[C++] 백준 10244번: 최대공약수들 - Math

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

10244번: 최대공약수들

---

 

구간 l ~ r 까지의 원소들의 최대공약수를 구했을 경우, 나올 수 있는 정수의 개수를 구하는 문제이다.

우선 주어지는 원소는 100 이하의 자연수이므로, 최대공약수의 개수도 최대 100개임을 알 수 있다.

 

하지만 i ~ n까지의 부분 집합을 하나하나 계산하기에는 시간적인 문제가 있으므로 이를 완전 탐색으로 접근하기에는 무리가 있어 보였다.

그래서 생각한 것은 1 ~ 100 정수가 나오는지 나오지 않는지에 대한 여부를 판단하고자 접근했다.

쉽게 말해, 100 * N 번의 탐색 만으로 문제를 해결하도록 접근했다.

 

이를 위해 먼저 찾고자 하는 자연수와 현재까지 진행한 부분 집합의 최대공약수를 비교해야한다.

만약 현재까지 진행한 부분 집합의 최대공약수가 찾고자하는 자연수로 나누어떨어지지 않는다면, 부분집합을 리셋해준다.

만약 나누어진다면 아직은 가능성이 있으므로 부분집합의 크기를 키워주면 된다.

 

#include <iostream>
#include <set>
#include <vector>
using namespace std;
bool check[101];
int gcd(int x, int y){
    return !y ? x : gcd(y, x%y);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, x;
    while(1){
        set<int>s;
        cin >> n;
        if(!n) break;
        vector<int>v(n);
        for(int i=0; i<n; i++) cin >> v[i];
        for(int i=1; i<101; i++){
            if(check[i]) continue;
            x=v[0];
            for(int j=0; j<n; j++){
                if(x%i) x=v[j];
                else x=gcd(x, v[j]);
                s.insert(x);
                check[x]=true;
            }
        }
        cout << s.size() << "\n";
        fill(check, check+101, 0);
    }
}