結果
問題 | No.546 オンリー・ワン |
ユーザー | nobuta05 |
提出日時 | 2022-04-07 01:15:06 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 2,522 bytes |
コンパイル時間 | 1,544 ms |
コンパイル使用メモリ | 146,020 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 14:49:21 |
合計ジャッジ時間 | 1,926 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 4 ms
6,944 KB |
testcase_09 | AC | 8 ms
6,940 KB |
testcase_10 | AC | 10 ms
6,944 KB |
ソースコード
import std.stdio, std.string, std.conv; import std.algorithm, std.math; import std.range; import std.container.rbtree, std.container.dlist; import std.container.binaryheap, std.container.array; import std.typecons; // import std.meta; alias mstring = char[]; const long INF = 1L << 60L; // const long mod = 1_000_000_000 + 7; const long mod = 998_244_353L; void chmin (T)(ref T x, T y) { x = min(x, y); } void chmax (T)(ref T x, T y) { x = max(x, y); } // 単一の数値を取得 // readln.chomp.to!int; // or // int a; // readf("%s\n", a); // 複数の数値を取得(可変数個の場合推奨) // readln.chomp.split.map!(to!long).array // 複数の数値を取得(固定数個の場合、推奨) // int a, b; // readf("%s %s\n", &a, &b); // インデントを一個ずらして複数の数値を取得(累積和とかで1-indexedの方が良い時がある) // long[] vs = readln.chomp.split.map!(to!long).array; // vs = [0L] ~ vs; // 小数点は以下で指定 // double ret = 10.0; // writefln("%.12f", ret); // 配列の最後の要素は arr[$-1] でアクセスできる long gcd (long m, long n) { if (m < n) swap (m, n); if (n == 0) return m; return gcd(n, m % n); } int N; long L, H; long[] cs; long calc (long h) { long ret = 0L; // tot0: どれでも割り切れない数の個数 long ttl = 0L; foreach (bits; 1 .. (1 << N)) { long mul = 1L; int cnt = 0; foreach (j; 0 .. N) if ((bits >> j) & 1) { long g = gcd(mul, cs[j]); long m = cs[j] / g; if (mul > INF / m) mul = INF; else mul *= cs[j] / g; cnt++; } if (cnt % 2 == 1) ttl += h / mul; else ttl -= h / mul; } long tot0 = h - ttl; // Ciのみで割り切れる数の個数をretに足していく foreach (i; 0 .. N) { long tot = 0L; foreach (bits; 1 .. (1 << N)) { if ((bits >> i) & 1) continue; long mul = 1L; int cnt = 0; foreach (j; 0 .. N) if ((bits >> j) & 1) { long g = gcd(mul, cs[j]); long m = cs[j] / g; if (mul > INF / m) mul = INF; else mul *= cs[j] / g; cnt++; } if (cnt % 2 == 1) tot += h / mul; else tot -= h / mul; } ret += h - (tot0 + tot); } return ret; } void main () { readf("%s %s %s\n", &N, &L, &H); cs = readln.chomp.split.map!(to!long).array; long ret = calc(H) - calc(L - 1); writeln(ret); }