結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー takey
提出日時 2024-05-30 02:48:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,965 bytes
コンパイル時間 6,993 ms
コンパイル使用メモリ 278,680 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-20 21:06:21
合計ジャッジ時間 4,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES  // M_PI等のフラグ
#include <bits/stdc++.h>
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define intceil(a,b) ((a+(b-1))/(b))
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long,long>;
const long long INF = LONG_LONG_MAX - 1001001001001001;
void chmax(ll& x, ll y) { x = max(x,y); }
void chmin(ll& x, ll y) { x = min(x,y); }
string vs = "URDL";  // 上右下左
vector<ll> vy = { -1, 0, 1, 0 };
vector<ll> vx = { 0, 1, 0, -1 };


void solve() {
    ll N, L, H; cin >> N >> L >> H;
    vector<ll> C(N);
    for(ll i=0; i<N; i++) cin >> C[i];

    // n(c0 ∪ c1 ∪ c2 ∪ ...) を求める
    ll all = 0;
    for(ll bit=1; bit<(1<<N); bit++) {
        ll popcnt = __builtin_popcountll(bit);
        ll div = 1;
        for(ll d=0; d<N; d++) {
            if (bit>>d&1) {
                div = lcm(div, C[d]);
            }
        }
        ll cntH = H/div;
        ll cntL = (L-1LL)/div;
        if (popcnt%2 == 0) all -= (cntH-cntL);
        else all += (cntH-cntL);
    }

    // n(C[i]以外の和集合)を求めて、C[i]のみで割り切れるものの個数を数え上げる
    ll ans = 0; // C[i]のみで割り切れるものの個数
    for(ll i=0; i<N; i++) {
        ll res = 0; // n(C[i]以外の和集合)
        for(ll bit=1; bit<(1<<N); bit++) {
            if (bit>>i&1) continue;
            ll popcnt = __builtin_popcountll(bit);
            ll div = 1;
            for(ll d=0; d<N; d++) {
                if (bit>>d&1) {
                    div = lcm(div, C[d]);
                }
            }
            ll cntH = H/div;
            ll cntL = (L-1LL)/div;
            if (popcnt%2 == 0) res -= (cntH-cntL);
            else res += (cntH-cntL);
        }
        ans += all-res;
    }
    cout << ans << endl;
}


// 別解
void solve2() {
    ll N, L, H; cin >> N >> L >> H;
    vector<ll> C(N);
    for(ll i=0; i<N; i++) cin >> C[i];

    // C[i]で割り切れる数を全体集合としたときに、
    // n(C[i]以外の和集合)を求めて、C[i]のみで割り切れるものの個数を数え上げる
    ll ans = 0; // C[i]のみで割り切れるものの個数の和
    for(ll i=0; i<N; i++) {
        ll res = 0; // C[i]のみで割り切れるものの個数
        for(ll bit=1; bit<(1<<N); bit++) {
            if (bit>>i&1) {
                ll popcnt = __builtin_popcountll(bit);
                ll div = 1;
                for(ll d=0; d<N; d++) {
                    if (bit>>d&1) {
                        div = lcm(div, C[d]);
                    }
                }
                ll cntH = H/div;
                ll cntL = (L-1LL)/div;
                if (popcnt%2 == 0) res -= (cntH-cntL);
                else res += (cntH-cntL);
            }
        }
        ans += res;
    }
    cout << ans << endl;
}


int main() {
    solve2();
    return 0;
}
0