結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー hashiryo
提出日時 2018-04-22 19:27:24
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,188 bytes
コンパイル時間 488 ms
コンパイル使用メモリ 60,028 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 07:02:53
合計ジャッジ時間 1,155 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
//  main.cpp
//  ProCon
//
//  Created by hashimotoryoma on 2017/08/20.
//  Copyright © 2017年 hashimotoryoma. All rights reserved.
//


#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

typedef long long ll;

int N;
ll L, H;
ll C[11];
ll ans;

ll gcd(ll x,ll y){
    return y==0? x:gcd(y,x%y);
}

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

ll lcmC[1<<11];

ll solve(int d,int num,int s){
    int e = num&1? 1:-1;
    if(d == N)
        return e*num*(H/lcmC[s]-(L-1)/lcmC[s]);
    ll res=0;
    res += solve(d+1,num,s);
    res += solve(d+1,num+1,s|(1<<d));
    return res;
}

int main() {
    // insert code here...    return 0;
  //////
    // input from txt
    /*
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    std::ofstream out("output.txt");
    std::cout.rdbuf(out.rdbuf());
   ///////
     */
    cin >> N >> L >> H;
    for(int i=0;i<N;i++){
        cin >> C[i];
    }
    
    int total = 1 << N;
    lcmC[0] = 1;
    for(int s = 0;s < total;s++){
        for(int u=0;u<N;u++){
            lcmC[s|(1<<u)] = lcm(lcmC[s],C[u]);
        }
    }
    ans = solve(0,0,0);
    cout << ans << endl;
    
    return 0;
}
0