結果

問題 No.546 オンリー・ワン
ユーザー mban
提出日時 2017-07-17 16:25:17
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,781 bytes
コンパイル時間 944 ms
コンパイル使用メモリ 105,856 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-10-08 06:52:10
合計ジャッジ時間 1,871 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static void Main()
    {
        new Magatro().Solve();
    }
}

class Magatro
{
    private int N, L, H;
    private int[] C;

    private long LL = 0, HH = 0;

    private void Scan()
    {
        var nlh = Console.ReadLine().Split(' ');
        N = int.Parse(nlh[0]);
        L = int.Parse(nlh[1]);
        H = int.Parse(nlh[2]);
        C = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    }

    private long LCM(long a, long b)
    {
        return (a * b) / GCD(a, b);
    }

    private long GCD(long a, long b)
    {
        if (a < b)
        {
            Swap(ref a, ref b);
        }
        long r = a % b;
        while (r > 0)
        {
            a = b;
            b = r;
            r = a % b;
        }
        return b;
    }

    private void Swap<T>(ref T a, ref T b)
    {
        T t = a;
        a = b;
        b = t;
    }

    private void S(int n, int c, long l, int t, ref long o)
    {
        if (n == N)
        {
            if (c == 0)
            {
                return;
            }
            long p = t / l * c;
            if (c % 2 == 1)
            {
                o += p;
            }
            else
            {
                o -= p;
            }
            return;
        }
        if (l > t)
        {
            return;
        }
        S(n + 1, c, l, t, ref o);
        S(n + 1, c + 1, LCM(C[n], l), t, ref o);
    }

    public void Solve()
    {
        Scan();
        S(0, 0, 1, H, ref HH);
        S(0, 0, 1, L - 1, ref LL);
        Console.WriteLine(HH - LL);
    }
}
0