백준 1565번 수학[C++]

1. 문제 풀이

 배열 M의 모든 숫자들의 최대공약수를 G라고 하자. 이때, G의 약수는 배열 M의 모든 수의 약수이다. 따라서 G의 약수를 구해 따로 저장한다. G는 1,000,000,000 이하의 수이고,  약수 개수의 최대값은 G가 831,600일 때 180개를 가진다. D의 배열 내 모든 숫자들의 최소공배수를 L이라고 하자. G의 임의의 약수 g가 L로 나누어 떨어진다면 문제에서 요구한 숫자임을 판단할 수 있다.

 

1. L을 계산하던 도중 G보다 값이 커진다면 문제에서 요구한 조건을 성립하는 수가 없으므로 0을 출력하고 종료하면 된다.

 

2. G가 1e9이고 계산이 아직 남은 L이 1e9보다 작지만 비슷한 값이라면 오버플로우가 발생할 수 있으므로 L은 long long 타입으로 선언하였다.

 

문제를 풀이하는 로직은 처음부터 맞았으나 하나의 실수로 맞왜틀을 시전 하였다...

// 최대 공약수의 약수를 구한다.
vi divisor{1, g};
for(int i = 2; i * i <= g; i++){
  if(g%i) continue;
  int t = g / i;
  divisor.pb(i);
  if(t != i) divisor.pb(t);
}

 

이유는 다음과 같다. 약수를 저장하는 divisior 벡터에 1과 g를 먼저 넣어놓고 2부터 확인하면서 약수를 추가해 주었는데, 최대공약수 g가 1인 경우 divisor 벡터에 1이 두 번 들어가게 되어 틀렸다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;
int a[55], b[55];

int main() {
  fastio(nullptr, false);

  // input
  cin >> n >> m;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) cin >> b[i];

  // 배열 b의 최대 공약수를 구한다.
  int g = b[0];  
  for(int i = 1; i < m; i++) g = gcd(g, b[i]);

  ll l = a[0];
  for(int i = 1; i < n; i++){
    if(l > g){
      cout << 0;
      return 0;
    }
    l = lcm(l, a[i]);
  }

  // solve
  // 최대 공약수의 약수를 구한다.
  vi divisor;
  for(int i = 1; i * i <= g; i++){
    if(g%i) continue;
    int t = g / i;
    divisor.pb(i);
    if(t != i) divisor.pb(t);
  }

  int ans{};
  sort(all(divisor));
  auto it = lower_bound(all(divisor), l);
  while(it < divisor.end()){
    if((*it) % l == 0) ans++;
    it++;
  }

  // output
  cout << ans;
}

 

3. 제출 결과