結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー Yoshiki Yokota
提出日時 2024-07-13 12:57:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,270 bytes
コンパイル時間 2,803 ms
コンパイル使用メモリ 247,104 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-13 12:57:58
合計ジャッジ時間 3,333 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<long long>;

#ifdef LOCAL
bool DEBUG = true;
#else
bool DEBUG = false;
#endif

#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) REP2(i, 0, n)
#define REP2(i, l, r) for (long long i = (l); (i) < (long long)(r); ++(i))
#define REP3(i, l, r, s) for (long long i = (l); (i) < (long long)(r); (i) += (s))
#define rep(i, ...) OVERLOAD_REP(__VA_ARGS__, REP3, REP2, REP1)(i, __VA_ARGS__)

// for debug
#define OVERLOAD_DEBUG(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, name, ...) name
#define DUMP1(a) if (DEBUG) {cerr << "line: " << __LINE__ << ", " << #a << ": "; dump(a); cerr << endl;};
#define DUMP2(a, ...) if (DEBUG) {DUMP1(a); DUMP1(__VA_ARGS__);};
#define DUMP3(a, ...) if (DEBUG) {DUMP1(a); DUMP2(__VA_ARGS__);};
#define DUMP4(a, ...) if (DEBUG) {DUMP1(a); DUMP3(__VA_ARGS__);};
#define DUMP5(a, ...) if (DEBUG) {DUMP1(a); DUMP4(__VA_ARGS__);};
#define DUMP6(a, ...) if (DEBUG) {DUMP1(a); DUMP5(__VA_ARGS__);};
#define DUMP7(a, ...) if (DEBUG) {DUMP1(a); DUMP6(__VA_ARGS__);};
#define DUMP8(a, ...) if (DEBUG) {DUMP1(a); DUMP7(__VA_ARGS__);};
#define DUMP9(a, ...) if (DEBUG) {DUMP1(a); DUMP8(__VA_ARGS__);};
#define DUMP10(a, ...) if (DEBUG) {DUMP1(a); DUMP9(__VA_ARGS__);};
#define debug(...) OVERLOAD_DEBUG(__VA_ARGS__, DUMP10, DUMP9, DUMP8, DUMP7, DUMP6, DUMP5, DUMP4, DUMP3, DUMP2, DUMP1)(__VA_ARGS__)

// デバッグ用
template<typename T> void dump(T a) { cerr << a;}

#if __cplusplus > 201703L
long long bit_count(long long x) { return popcount((ull)x); }
#else 
long long bit_count(long long x) { return __builtin_popcountll(x); }
#endif

struct Bitset {
    long long bit;

    Bitset(long long bit = 0) : bit(bit) {}

    void set(long long pos, bool val = true) { val? bit |= (1ll << pos): bit &= ~(1ll << pos); }
    void set(vector<long long> pos, bool val = true) { for (auto x : pos) set(x, val);}

    void flip(long long pos) { bit ^= (1ll << pos); }
    void reset(long long pos) { bit &= ~(1ll << pos); }
    void reset(vector<long long> pos) { for (auto x : pos) reset(x);}
    bool test(long long pos) { return (bit >> pos) & 1ll; }
    long long count() { return bit_count(bit); }
    long long to_ll() { return bit; }
    operator long long() { return bit; }
    bool any() { return bit != 0; }
    bool none() { return bit == 0; }
    bool all(long long size) { return bit == (1ll << size) - 1;}

    // 自身がxの部分集合かどうか判定
    bool is_subset_of(Bitset x) { return (bit & x.bit) == bit; }
    // 自身がxの上位集合かどうか判定
    bool is_superset_of(Bitset x) { return (bit & x.bit) == x.bit; }
    // 自身がxの真部分集合かどうか判定
    bool is_proper_subset_of(Bitset x) { return bit != x.bit && (bit & x.bit) == bit; }
    // 自身がxの真上位集合かどうか判定
    bool is_proper_superset_of(Bitset x) { return bit != x.bit && (bit & x.bit) == x.bit; }
    // 自身がxと交差しているかどうか判定
    bool intersects(Bitset x) { return bit & x.bit; }
    
    Bitset& operator++() { bit = bit + 1; return *this; }
    Bitset operator&(Bitset x) { return bit & x.bit; }
    Bitset operator|(Bitset x) { return bit | x.bit; }
    Bitset operator^(Bitset x) { return bit ^ x.bit; }
    Bitset operator~() { return ~bit; }
    Bitset operator<<(long long x) { return bit << x; }
    Bitset operator>>(long long x) { return bit >> x; }
    Bitset& operator&=(Bitset x) { bit &= x.bit; return *this; }
    Bitset& operator|=(Bitset x) { bit |= x.bit; return *this; }
    Bitset& operator^=(Bitset x) { bit ^= x.bit; return *this; }
    Bitset& operator<<=(long long x) { bit <<= x; return *this; }
    Bitset& operator>>=(long long x) { bit >>= x; return *this; }
    bool operator==(Bitset x) { return bit == x.bit; }
    bool operator!=(Bitset x) { return bit != x.bit; }
    bool operator<(Bitset x) { return bit < x.bit; }
    bool operator>(Bitset x) { return bit > x.bit; }
    bool operator<=(Bitset x) { return bit <= x.bit; }
    bool operator>=(Bitset x) { return bit >= x.bit; }
    bool operator==(long long x) { return bit == x; }
    bool operator!=(long long x) { return bit != x; }
    bool operator<(long long x) { return bit < x; }
    bool operator>(long long x) { return bit > x; }
    bool operator<=(long long x) { return bit <= x; }
    bool operator>=(long long x) { return bit >= x; }

    friend istream& operator>>(istream& is, Bitset& x) { return is >> x.bit; }
    friend ostream& operator<<(ostream& os, Bitset& x) { 
        os << (x.bit & 1) << " ";
        x.bit >>= 1;

        while (x.bit) {
            os << (x.bit & 1) << " ";
            x.bit >>= 1;
        }
        return os; 
    }
};


int main() {
    ll N, L, H;
    cin >> N >> L >> H;

    vll C(N);
    rep(i, N) cin >> C[i];

    ll ans = 0;

    for (Bitset bit = 1; bit < (1ll << N); ++bit) {
        ll prod = 1;
        ll cnt = 0;

        rep(i, N) {
            if (bit.test(i)) {
                prod = lcm(prod, C[i]);
                cnt++;
            }
        }

        ll sign = (cnt % 2 == 0)? -1: 1;
        ans += sign * (H / prod - (L - 1) / prod) * cnt;
    }
    
    cout << ans << endl;

    return 0;
}
0