結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー 橋本明日雄
提出日時 2026-04-11 00:18:06
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,850 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,205 ms
コンパイル使用メモリ 412,360 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-04-11 00:18:15
合計ジャッジ時間 8,103 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//高速化オプション
#ifdef EARTH999
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define NDEBUG
#endif
// 基本
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// 型名の省略
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T,class U>
using ump = unordered_map<T,U>;
// 定数
template <class T>
constexpr T INF = 0;
template <>
constexpr int INF<int> = 1001001001;
template <>
constexpr long long INF<long long> = 1LL << 61;
template <>
constexpr double INF<double> = INF<long long>;
template <>
constexpr long double INF<long double> = INF<long long>;
// 便利関数
bool is_palindrome(const string& s) { return equal(s.begin(), s.end(), s.rbegin()); }
template<class T>
bool is_palindrome(const vector<T>& s) { return equal(s.begin(), s.end(), s.rbegin()); }
ll floor_sqrt(ll x){
	ll y = sqrt(x);
	while (y * y > x) y--;
	while ((y+1) * (y+1) <= x) y++;
	return y;
}
bool is_sqrt(ll x){
    ll y = floor_sqrt(x);
    if(y*y == x) return true;
    else return false;
}
ll pow_ll(ll a,ll b){
    ll ret = 1;
    while(b > 0){
        if(b&1) ret *= a;
        a *= a;b >>= 1;
    }
    return ret;
}
template <class T>
T ceil(T a,T b){
    return (a+b-1)/b;
}
//宣言兼入力
template <class T,class U>
istream& operator>>(istream& i,pair<T,U>& p){
    i >> p.first >> p.second;
    return i;
}
#define INT(...) int __VA_ARGS__; input(__VA_ARGS__);
#define LL(...) long long __VA_ARGS__; input(__VA_ARGS__);
#define DB(...) double __VA_ARGS__; input(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; input(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; input(__VA_ARGS__);
#define VEC(type,a,n) vector<type> a((n)); for(int i = 0;i < (n);i++) cin>>a[i];
#define VVEC(type,g, h, w) vector<vector<type>> g(h,vector<type>(w)); for(int i = 0;i < h;i++) for(int j = 0;j < w;j++) cin >> g[i][j];
// 入出力処理
template <class... T>
void input(T &...a)
{
    (cin >> ... >> a);
}
template <class T, class... Ts>
void print(const T &a, const Ts &...b)
{
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}
void print(){
    cout << '\n';
}
// 繰り返し処理
#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SUM(s,a) vector<ll> s((a).size()+1); s[0]=0LL; for(int i = 0;i < (a).size();i++) s[i+1] = s[i]+a[i];
#define ZERO(a) for(int i = 0;i < (a).size();i++) a[i]--;
#define MOD(a,b) (((a)%(b)+(b))%(b)) //a mod bを0以上m未満の形で表す。
// 配列処理
// 最小・最大処理
template <class T,class U>
inline bool chmax(T &a,U b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T,class U>
inline bool chmin(T &a,U b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
// 追加ライブラリ

/// ここからコードを書く

int main()
{
    cin.tie(0);
    LL(n,l,h)
    VEC(ll,c,n)
    vc<ll> b(1<<n);
    REP(bit,1<<n){
        ll skb = 1;
        REP(bi,n) if((bit>>bi)&1) skb = (skb/gcd(skb,c[bi]) > INF<ll>/c[bi] ? INF<ll> : lcm(skb,c[bi]));
        b[bit] = h/skb-(l-1)/skb;
    }
    REP(i,n){
        REP(bit,1<<n){
            if(!((bit>>i)&1)){
                b[bit] -= b[bit^(1<<i)];
            }
        }
    }
    ll ans = 0;
    REP(i,1<<n){
        int pc = popcount(unsigned(i));
        if(pc == 1) ans += b[i];
    }
    print(ans);
    return 0;
}
0