結果
問題 | No.546 オンリー・ワン |
ユーザー | Risen |
提出日時 | 2017-07-16 10:00:51 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 1,573 bytes |
コンパイル時間 | 914 ms |
コンパイル使用メモリ | 111,488 KB |
実行使用メモリ | 28,352 KB |
最終ジャッジ日時 | 2024-10-08 04:08:19 |
合計ジャッジ時間 | 1,828 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
26,444 KB |
testcase_01 | AC | 29 ms
26,288 KB |
testcase_02 | AC | 29 ms
26,352 KB |
testcase_03 | AC | 27 ms
24,372 KB |
testcase_04 | AC | 29 ms
25,972 KB |
testcase_05 | AC | 27 ms
26,432 KB |
testcase_06 | AC | 28 ms
26,352 KB |
testcase_07 | AC | 28 ms
26,552 KB |
testcase_08 | AC | 27 ms
26,224 KB |
testcase_09 | AC | 29 ms
28,352 KB |
testcase_10 | AC | 29 ms
26,448 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Specialized; using System.Linq; class Solution { static long GCD(long m, long n) { if (m < n) { return GCD(n, m); } while (n != 0) { var t = n; n = m % n; m = t; } return m; } static long DivisibleCount(long lo, long high, long div) { return high / div - (lo - 1) / div; } static void Main() { var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); var n = vals[0]; var l = vals[1]; var h = vals[2]; var c = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); long sum = 0; // 包除原理により差集合を得る // n(1のみ) = n(1) - n(1∩2∪3∪..x) for (int pattern = 1; pattern < (1 << n); pattern++) { var bits = new BitVector32(pattern); long div = 1; var count = 0; for (int i = 0; i < n; i++) { if (bits[1 << i]) { div = (div * c[i]) / GCD(div, c[i]); count++; } } var set = DivisibleCount(l, h, div); if (count == 1) { sum += set; } else { // x∩なので正負反転 sum -= ((count % 2 == 1) ? -1 : 1) * set * (count); } } Console.WriteLine(sum); } }