Codeforces Round #641 (Div. 1) A. Orac and LCM

gcdを求めたいので素因数ごとに独立に考えて、最後に掛け合わせても問題ない。

例えば数列が $(2^0, 2^1, 2^2, 2^3)$ であったとする。このときのlcmの集合は

$\text{lcm}(2^0, 2^1) = 2^{\max(0, 1)}$
$\text{lcm}(2^0, 2^2) = 2^{\max(0, 2)}$
$\text{lcm}(2^0, 2^3) = 2^{\max(0, 3)}$
$\text{lcm}(2^1, 2^2) = 2^{\max(1, 2)}$
$\text{lcm}(2^2, 2^3) = 2^{\max(2, 3)}$

となる。このときの $\gcd$ は $2^{\max(0, 1)}$ となる。このように指数が小さい方から2番目の値のものが $\gcd$ の指数となる。

あとは素因数ごとに指数が小さい方から2番目のものを列挙していく。指数が0のものもすべて列挙すると $O(n \times ($ 素数の個数 $))$ かかってしまうので、各数の素因数のみを参照するように工夫する。

$\text{num} \lbrack i \rbrack = ($ 素因数 $i$ を約数にもつ数の個数 $)$ 、 $\text{mi} \lbrack i \rbrack = ($ 素因数 $i$ の指数の最小 $)$ 、 $\text{mi2} \lbrack i \rbrack = ($ 素因数 $i$ の指数の小さい方から2番目 $)$ とした配列を持つ。数 $A_i$ の素因数分解を行い、現れた素因数についてこれらの配列の更新を行う。これは $O(\sqrt{A_i})$ でできる。

配列を構成した後、 $\text{num} \lbrack i \rbrack = n$ であれば $i^{\text{mi2} \lbrack i \rbrack }$ を答えに掛け、 $\text{num} \lbrack i \rbrack = n-1$ であれば $i^{\text{mi} \lbrack i \rbrack }$ (最小の指数は0なので)を答えに掛ける。 $\text{num} \lbrack i \rbrack \leq n-2$ のときは2番目から小さい方の指数は0なので何もしなくても問題ない。

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
ll modpow(ll x, ll y) {  
    ll a = 1, p = x;  
    while(y > 0) {  
        if(y%2 == 0) {p = (p*p); y /= 2;}  
        else {a = (a*p); y--;}  
    }  
    return a;  
}  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    if(n == 2) {  
        cout << lcm(a[0], a[1]) << endl;  
        return 0;  
    }  
  
    vector<ll> num(200001), mi(200001, INF), mi2(200001, INF);  
    REP(i, n) {  
        ll t = a[i];  
        for(ll j=2; j*j<=t; j++) {  
            ll cnt = 0;  
            while(t%j == 0) {  
                cnt++;  
                t /= j;  
            }  
            num[j]++;  
            if(mi[j] > cnt) {  
                mi2[j] = mi[j];  
                mi[j] = cnt;  
            } else if(mi2[j] > cnt) {  
                mi2[j] = cnt;  
            }  
        }  
        if(t > 1) {  
            num[t]++;  
            if(mi[t] > 1) {  
                mi2[t] = mi[t];  
                mi[t] = 1;  
            } else if(mi2[t] > 1) {  
                mi2[t] = 1;  
            }  
        }  
    }  
  
    ll ans = 1;  
    FOR(i, 2, 200001) {  
        if(num[i] == n-1) ans *= modpow(i, mi[i]);  
        else if(num[i] == n) ans *= modpow(i, mi2[i]);  
    }  
    cout << ans << endl;  
  
    return 0;  
}

$\text{num} \lbrack i \rbrack = n-1$ のときに $i^{\text{mi2} \lbrack i \rbrack }$ を掛けてシステス落とした…

ferinの競プロ帳

競プロについてのメモ

Codeforces Round #641 (Div. 1) A. Orac and LCM