結果
問題 | No.546 オンリー・ワン |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
コンパイルメッセージ
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); } }