[AOJ] No. 0410 アカベコ20
問題
方針
参加するメンバーの組み合わせは \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません