結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー konishi
提出日時 2023-04-23 10:50:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,627 bytes
コンパイル時間 3,091 ms
コンパイル使用メモリ 248,600 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 18:42:58
合計ジャッジ時間 3,615 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<vector<int>> VII;
typedef vector<vector<ll>> VLL;
typedef vector<string> VS;

#define pii pair<int,int>
#define pll pair<ll,ll>
#define pis pair<int,string>
#define psi pair<string,int>
#define rep(i,num,n) for(int i=num;i<(int)(n);i++) //for_loop
#define rrep(i,num,n) for(int i=num-1;i>=(int)(n);i--) //reverse_for>
#define in(x,a,b) (a<=x && x<b)//範囲
#define reo return 0
#define all(v) v.begin(),v.end()
#define INF 2000000000
#define INFL 9000000000000000000

const long double pi = 3.1415926535897932384626433832795028841971L;
const ll MOD=1000000007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll CountMultiple(ll L,ll R,ll div){//[L,R]の範囲でdivで割り切れる個数
    if(R%div==0){
        if(L%div==0) return R/div-L/div+1;
        else return R/div-L/div;
    }else{
        if(L%div==0)return R/div-L/div+1;
        else return R/div-L/div;
    }
}

int main(){
    ll N,L,H;
    cin>>N>>L>>H;
    VL C(N);rep(i,0,N)cin>>C[i];
    ll ans=0;
    rep(i,0,N){
        VL cc;
        ll d=0;
        rep(j,0,N)if(i!=j)cc.push_back(C[j]);
    rep(bit,0,(1<<(N-1))){
        ll lc=C[i];
        int cnt=0;
        rep(j,0,N-1)if(bit & (1<<j))lc=lcm(lc,cc[j]),cnt++;

        ll c=CountMultiple(L,H,lc);
        if(cnt%2==0)d+=c;
        else d-=c;
    }
    ans+=d;
    }
    cout<<ans<<endl;
}
0