結果
問題 | No.546 オンリー・ワン |
ユーザー | te-sh |
提出日時 | 2017-07-15 00:08:07 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,921 bytes |
コンパイル時間 | 1,880 ms |
コンパイル使用メモリ | 170,964 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 20:59:20 |
合計ジャッジ時間 | 2,594 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,944 KB |
testcase_07 | AC | 10 ms
6,940 KB |
testcase_08 | AC | 9 ms
6,944 KB |
testcase_09 | AC | 33 ms
6,940 KB |
testcase_10 | AC | 26 ms
6,944 KB |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; import std.container; // SList, DList, BinaryHeap import std.typecons; // Tuple, Nullable, BigFlags import std.math; // math functions import std.numeric; // gcd, fft import std.bigint; // BigInt import std.random; // random import std.bitmanip; // BitArray import core.bitop; // bit operation import std.regex; // RegEx import std.uni; // unicode void main() { auto rd = readln.split.to!(BigInt[]), n = rd[0].to!int, l = rd[1], h = rd[2]; auto c = readln.split.to!(BigInt[]); writeln(f(n, c, h) - f(n, c, l-1)); } auto f(int n, BigInt[] c, BigInt m) { auto r = BigInt(0); foreach (i; 1..1 << n) { auto d = c.indexed(i.bitsSet).array; auto t = (-1) ^^ (i.popcnt - 1) * i.popcnt * calc(m, d); r += t; } return r; } auto calc(BigInt n, BigInt[] c) { auto l = c.fold!((a, b) => lcd(a, b)); auto r = n / l; return r; } BigInt lcd(BigInt a, BigInt b) { return a / gcd(a, b) * b; } BigInt gcd(BigInt a, BigInt b) { if (a < b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } pragma(inline) { pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; } pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); } pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); } pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); } pure T bitSet(T)(T n, size_t s, size_t e) { return n | ((T(1) << e) - 1) & ~((T(1) << s) - 1); } pure T bitReset(T)(T n, size_t s, size_t e) { return n & (~((T(1) << e) - 1) | ((T(1) << s) - 1)); } pure T bitComp(T)(T n, size_t s, size_t e) { return n ^ ((T(1) << e) - 1) & ~((T(1) << s) - 1); } import core.bitop; pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); } pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); } pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); } }