ARC114 振り返りメモ (A問題まで)

#結果
0完で, レート変化は748→695(-53)

#A問題 ( Not coprime )
###概要

2以上50以下のN個の自然数のどれとも互いに素にならない最小の自然数を求める.

###方針
X [ i ] と現状の答えと互いに素でなければ, X [ i ] の最小の素因数を現状の答えにかけていくという方針で解いたが, X = {15, 20} のような場合に, 12 と出力してしまったりするので, いい方針では無かった.
答えは必ず素数の積になるので, 全ての素数の積の組み合わせを全探索すれば良い.
また, その際にbit全探索を使う.

C++ での実装例は以下のようになる.

a.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

const ll LINF = (1LL<<60)-1;

ll gcd(ll x, ll y) {
    if (x % y == 0) return y;
    else return gcd(y, x % y);
}

int main() {
    ll n; cin >> n;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];
    vector<ll> p = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    ll ans = LINF; // 答えは十分に大きい値で初期化
    for (ll bit = 0; bit < (1 << (ll)p.size()); bit++) {
        bool ok = true;
        ll sum = 1;
        rep(i, (ll)p.size()) {
            if (bit & (1 << i)) {
                sum *= p[i];
            }
        }
        for (auto x_val : x) {
            if (gcd(x_val, sum) == 1) {
                ok = false;
            }
        }
        if (ok) ans = min(ans, sum);
    }
    cout << ans << endl;
}