문제링크
문제
N개의 수로 이루어진 배열 A과 정수 K가 주어진다. 0 ≤ p < q < r < N 이면서, A[p] * A[q] * A[r]이 K로 나누어 떨어지는 (p, q, r) 쌍의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 2,000, 1 ≤ K ≤ 1,000,000)
둘째 줄에 배열 A에 포함되어 있는 수가 A[0]부터 A[N-1]까지 순서대로 주어진다. (1 ≤ A[i] ≤ 100,000,000)
풀이 유형
풀이
단순한 완전 탐색으로는 풀리지 않는 문제다. 이 문제를 풀기 위해서 집중해서 봐야 할 것은 K의 범위다. K는 아무리 커도 100만 이하의 수다. 그리고 아래, 일련의 소수의 곱을 보자.
1
2 * 3 * 5 * 7 * 11 * 13 * 17 = 510,510
연속한 소수 17까지의 곱이 100만 이하의 마지노선이다. 여기서 우리는 대략 짐작이 가기 시작한다. K와 배열 A의 원소 사이의 최대공약수(GCD)의 종류가 그리 많이 존재하지 않을 것이라는 사실을 말이다. 당장 1,000,000도 2^6 * 5^6 이라 49가지 밖에 존재하지 않는다.
결론을 말하자면, 2000개의 원소가 아니라, 각각의 최대공약수를 배열로 삼아, 탐색을 진행시켜주면 되는 것이다.
주의 할 점은 같은 최대공약수를 갖는 집합 내에서도 곱샘이 이뤄질 수 있기 때문에 이를 분기할 필요성이 있다.
마무리
풀이는 간단하지만, 의외로 최대공약수라는 개념을 떠올리기가 어렵다. 무지성 완전탐색에 발을 들이민 순간 시간초과를 마주하게 되는 것이다. 이런 문제들을 풀 때 마다 왜 이 분야가 수학이 중요한지 다시금 깨닫는다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long int ll;
ll Euclid(ll a, ll b){
if(b == 0) return a;
return Euclid(b, a%b);
}
ll N, K;
ll anw = 0;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>N>>K; anw = 0;
map<ll, ll> dic;
vector<pair<ll, ll>> v;
for(int i=0; i<N; i++){
ll n; cin >>n;
ll k = Euclid(n, K);
if(dic.find(k) == dic.end()) dic[k] = 0;
dic[k]++;
}
map<ll, ll>::iterator iter = dic.begin();
for(; iter != dic.end(); iter++){
v.push_back(*iter);
}
for(int i=0; i<v.size(); i++){
if(v[i].first*v[i].first*v[i].first % K == 0 && v[i].second >= 3) anw += (v[i].second-2)*(v[i].second-1)*(v[i].second)/6;
}
for(int i=0; i<v.size(); i++){
for(int j=i+1; j<v.size(); j++){
if(v[i].first*v[i].first*v[j].first % K == 0 && v[i].second >= 2) anw += (v[i].second-1)*(v[i].second)*(v[j].second)/2;
if(v[j].first*v[j].first*v[i].first % K == 0 && v[j].second >= 2) anw += (v[j].second-1)*(v[j].second)*(v[i].second)/2;
}
}
for(int i=0; i<v.size(); i++){
for(int j=i+1; j<v.size(); j++){
for(int k=j+1; k<v.size(); k++){
if(v[i].first*v[j].first*v[k].first % K == 0) anw += v[i].second*v[j].second*v[k].second;
}
}
}
cout<<anw<<endl;
}