Codeforces Round #613 (Div. 2) F - Classical?

問題ページ
Codeforces #613 (Div. 2) F. Classical? (R2800) - けんちょんの競プロ精進記録 のスタックの中に互いに素なものの個数を数える部分についてちょっと悩んだのでそこだけ書きます．

「スタックの中に が存在する． と互いに素なものの個数を数えろ．」という問題を解きます．

http://compro.tsutajiro.com/archive/181015_incexc.pdf のオイラーの 関数，Uncommon と同じように包除原理を適用します．補集合として互いに素でないものの個数を数えます．この個数は が素因数 が素因数 が素因数 と表される和集合の要素数です．素因数の個数は高々6個程度なので，包除原理をつかって数え上げることができます．

メビウス関数 を用いると，互いに素でないものの個数は で表せます．包除原理で数えない，素数の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;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    const ll m = 100000;  
    vector<ll> b(m+1);  
    REP(i, n) b[a[i]]++;  
    vector<vector<ll>> pdiv(m+1);  
    vector<ll> min_factor(m+1, -1);  
    min_factor[0] = 0, min_factor[1] = 1;  
    FOR(i, 2, m+1) {  
        if(min_factor[i] != -1) continue;  
        pdiv[i].push_back(i);  
        min_factor[i] = i;  
        for(ll j=i*2; j<=m; j+=i) {  
            pdiv[j].push_back(i);  
            if(min_factor[j] == -1) min_factor[j] = i;  
        }   
    }  
  
    stack<ll> st;  
    vector<ll> cnt(m+1);  
    auto add = [&](ll x) {  
        st.push(x);  
        const ll sz = pdiv[x].size();  
        FOR(i, 1, 1LL<<sz) {  
            ll val = 1;  
            REP(j, sz) if(i&1LL<<j) val *= pdiv[x][j];  
            cnt[val]++;  
        }  
    };  
    auto erase = [&] {  
        ll x = st.top(); st.pop();  
        const ll sz = pdiv[x].size();  
        FOR(i, 1, 1LL<<sz) {  
            ll val = 1;  
            REP(j, sz) if(i&1LL<<j) val *= pdiv[x][j];  
            cnt[val]--;  
        }  
    };  
    auto check = [&](ll x) {  
        ll ret = st.size();  
        const ll sz = pdiv[x].size();  
        FOR(i, 1, 1LL<<sz) {  
            ll val = 1;  
            REP(j, sz) if(i&1LL<<j) val *= pdiv[x][j];  
            if(__builtin_popcountll(i)%2) ret -= cnt[val];  
            else ret += cnt[val];  
        }  
        return ret > 0;  
    };  
  
    ll ret = 0;  
    REP(i, n) chmax(ret, a[i]);  
    FOR(i, 1, m+1) {  
        vector<ll> v;  
        for(ll j=i; j<=m; j+=i) if(b[j]>0) v.push_back(j/i);  
        reverse(ALL(v));  
        for(auto j: v) {  
            while(check(j)) {  
                ll t = st.top() * i;  
                chmax(ret, t / __gcd(j*i, t) * j*i);  
                erase();  
            }  
            add(j);  
        }  
        while(st.size()) erase();  
    }  
    cout << ret << endl;  
  
    return 0;  
}