結果

問題 No.546 オンリー・ワン
ユーザー 0x19f0x19f
提出日時 2017-07-15 20:02:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,054 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 83,056 KB
実行使用メモリ 17,948 KB
最終ジャッジ日時 2024-04-16 21:53:30
合計ジャッジ時間 4,485 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 16 ms
5,376 KB
testcase_07 WA -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;
typedef long long ll;

int N;
ll L, H, C[10];

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

ll div_count(ll p) {
  ll l = (L + (p - L % p) % p), h = (H - H % p);
  ll n = (h - l) / p + 1;
  return n;
}

int main(void) {
  cin >> N >> L >> H;
  REP(i, 0, N) cin >> C[i];

  ll fact[11];
  fact[0] = 1;
  REP(i, 0, 10) fact[i + 1] = fact[i] * (i + 1);

  ll ans = 0;
  REP(i, 1, N + 1) {
    ll a[20];
    REP(i, 0, N) a[i] = i;
    set< vector<ll> > st;
    do {
      vector<ll> v;
      REP(j, 0, i) v.push_back(a[j]);
      st.insert(v);
    } while(next_permutation(a, a + N));

    ll cnt = 0;
    for(vector<ll> v : st) {
      ll p = 1;
      REP(i, 0, v.size()) p = lcm(p, C[v[i]]);
      cnt += div_count(p);
    }
    cnt /= fact[i];

    ans += (i % 2 == 0 ? -1 : 1) * i * cnt;
  }
  cout << ans << endl;
}
0