結果
問題 | No.546 オンリー・ワン |
ユーザー |
![]() |
提出日時 | 2018-10-23 15:15:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 1,399 ms |
コンパイル使用メモリ | 160,240 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-19 04:07:47 |
合計ジャッジ時間 | 2,114 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; i64 lcm(i64 a, i64 b) { return a / __gcd(a, b) * b; } void moebius(vi& ss) { int N = ss.size(); int n = 0; while (N > 1) { n++; N >>= 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < (1 << n); j++) { if (!(j & (1 << i))) { ss[j] -= ss[j | (1 << i)]; } } } } int main() { i64 n, l, h; cin >> n >> l >> h; vi as(n); for (int i = 0; i < n; i++) { cin >> as[i]; } vi cnt(1 << n); for (int i = 0; i < (1 << n); i++) { i64 m = 1; for (int j = 0; j < n; j++) { if ((i >> j) & 1) { m = lcm(m, as[j]); } } cnt[i] = h / m - (l - 1) / m; } moebius(cnt); i64 ans = 0; for (int i = 0; i < (1 << n); i++) { if (__builtin_popcount(i) == 1) { ans += cnt[i]; } } cout << ans << endl; }