[AOJ] No. 0410 アカベコ２０

2019年12月10日2019年12月17日

問題

方針

参加するメンバーの組み合わせは \( 2^{N} – 1\) 通りあるので、ビット全探索を行います。周期が同じメンバーが増えても必ず同じ公演に参加することになるので、参加するメンバーの組み合わせが増えることはありません。また、周期が \( 2, 3 \) のメンバーは周期がいるとき、周期 \( 6 \) で同じ公演に参加するので、周期が \( 6 \) のメンバーが増えても組み合わせは変わりません。

以上より、参加するメンバーの最小公倍数の数が答えになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main() {
    int N;
    cin >> N;
    ll p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    int n = 1<<N;
    set<ll> s;
    for (int i = 1; i < n; i++) {
        ll l = 1;
        for (int j = 0; j < N; j++) {
            if ((i & (1<<j)) != 0) {
                l = lcm(l, p[j]);
            }
        }
        s.insert(l);
    }
    cout << s.size() << "\n";
    return 0;
}