結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー imulan
提出日時 2017-07-16 20:41:37
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,017 bytes
記録
コンパイル時間 1,566 ms
コンパイル使用メモリ 169,596 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-08 04:28:50
合計ジャッジ時間 2,102 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

inline ll lcm(ll x, ll y)
{
    return x/__gcd(x,y)*y;
}

inline ll f(ll x, ll lim)
{
    return lim/x;
}

int main()
{
    int n;
    ll L,H;
    cin >>n >>L >>H;
    vector<ll> c(n);
    rep(i,n) cin >>c[i];

    ll ans = 0;
    rep(mask,1<<n)
    {
        ll m=1;
        rep(i,n)if(mask>>i&1)
        {
            m = lcm(m,c[i]);
            if(m>H) break;
        }

        int b = __builtin_popcount(mask);
        if(b%2==0) b = -b;
        ans += b*(f(m,H)-f(m,L-1));
    }
    cout << ans << endl;
    return 0;
}
0