백준 24537 (C++) 약수 계산

최초 업로드: 2025-11-18 02:07:47

최근 수정 시간: 2025-11-18 02:07:47

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 약수 계산

[문제 링크](https://www.acmicpc.net/problem/24537)

## 문제 설명

경아는 $N$($1 \le N \le 3 \cdot 10^5 $)개의 수를 이용해서 최대 공약수를 계산하는 놀이를 하고 있다. 경아가 가지고 있는 수는 모두 $1$ 이상 $10^6$ 이하의 정수이다.

경아가 하는 놀이의 진행 방식은 다음과 같다.

<ul>
	<li>임의의 수 $K$($ 1 \le K \le 10^6$)를 선택한다.</li>
	<li>가지고 있는 수 중에서 일부를 골라 고른 수의 최대 공약수가 $K$가 되게끔 만든다. 이 때, 수는 최대한 많이 골라야 한다. 수를 하나만 고른 경우 최대공약수는 그 수와 같은 걸로 생각한다.</li>
</ul>

경아는 이 놀이를 한참 하다가 피곤해졌다. 경아가 선택한 $Q$($ 1 \le Q \le 3 \cdot 10^5 $)개의 수가 주어졌을 때 대신 답을 계산해주는 프로그램을 작성해보자.

## 입력

첫째 줄에 경아가 가지고 있는 수의 개수 $N$ ($ 1 \le N \le 3 \cdot 10^5 $)이 주어진다.

둘째 줄에 경아가 가지고 있는 $N$개의 수 목록이 공백으로 구분되어 주어진다. 각 수는 $1$ 이상 $10^6$ 이하의 정수이다.

셋째 줄에 경아가 선택한 수의 개수 $Q$ ($ 1 \le Q \le 3 \cdot 10^5$)가 주어진다.

넷째 줄부터 $Q$줄에 걸쳐 경아가 선택한 수 $K$가 한 줄에 하나씩 주어진다. 각 수는 $1$ 이상 $10^6$ 이하의 정수이다.

## 출력

$Q$줄에 걸쳐, 가지고 있는 수에서 최대공약수가 $K$가 되게끔 가능한 한 많은 수를 골랐을 때 고를 수 있는 수의 개수를 출력한다. 만약 어떻게 골라도 최대 공약수가 $K$가 되게 만들 수 없다면 대신 $-1$을 출력한다.

## 풀이
최대 공약수가 k가 되도록 최대한 많은 수를 선택하려면 등장한 k의 배수들을 전부 선택하면 됩니다. 전부 선택해보고 최대공약수가 k와 같지 않으면 -1를 뱉으면 됩니다. 같은 k에 대해 한번씩만 계산을 한다면, 계산량이 대략 Nlog(1e6)까지 작아질 것이기에 시간 내에 통과합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1'000'001;

int cnt[MAX], dp[MAX];

int solve(int k) {
    if(dp[k]) return dp[k];

int gcdVal=-1;
 for(int i=k;i<MAX;i+=k) {
 if(cnt[i]) {
 dp[k] += cnt[i];
 if(gcdVal==-1) gcdVal=i;
 else gcdVal = gcd(gcdVal, i);
 }
 }
 if(gcdVal!=k) dp[k]=-1;
 return dp[k]; 
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) {
        int cur; cin >> cur;
        cnt[cur]++;
    }

int q; cin >> q;
 while(q--) {
 int k; cin >> k;
 cout << solve(k) << '\n';
 }
}
```