結果

問題 No.2119 一般化百五減算
ユーザー kakel-sankakel-san
提出日時 2022-11-04 22:38:53
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 2,855 bytes
コンパイル時間 2,957 ms
コンパイル使用メモリ 108,672 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2024-07-18 20:34:59
合計ジャッジ時間 4,719 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
19,328 KB
testcase_01 AC 26 ms
19,456 KB
testcase_02 AC 25 ms
19,200 KB
testcase_03 AC 25 ms
19,328 KB
testcase_04 AC 25 ms
19,328 KB
testcase_05 AC 26 ms
19,456 KB
testcase_06 AC 26 ms
19,328 KB
testcase_07 AC 25 ms
19,072 KB
testcase_08 AC 25 ms
19,328 KB
testcase_09 AC 25 ms
19,328 KB
testcase_10 AC 26 ms
19,072 KB
testcase_11 AC 26 ms
19,200 KB
testcase_12 AC 25 ms
19,072 KB
testcase_13 AC 24 ms
19,328 KB
testcase_14 AC 24 ms
19,328 KB
testcase_15 AC 25 ms
18,944 KB
testcase_16 AC 25 ms
19,072 KB
testcase_17 AC 25 ms
19,200 KB
testcase_18 AC 25 ms
19,200 KB
testcase_19 AC 25 ms
19,328 KB
testcase_20 AC 94 ms
25,088 KB
testcase_21 AC 26 ms
19,456 KB
testcase_22 AC 122 ms
24,960 KB
testcase_23 AC 120 ms
25,216 KB
testcase_24 AC 130 ms
25,088 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(int n) => Enumerable.Repeat(0, n).Select(_ => NList).ToArray();
    static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var m = NN;
        var dic = new Dictionary<int, int>();
        for (var i = 0; i < m; ++i)
        {
            var s = NList;
            s[1] %= s[0];
            if (s[1] < 0) s[1] += s[0];
            if (dic.ContainsKey(s[0]))
            {
                if (dic[s[0]] != s[1])
                {
                    WriteLine("NaN");
                    return;
                }
            }
            else dic[s[0]] = s[1];
        }
        for (var i = 0; i <= n; ++i)
        {
            var flg = true;
            foreach (var kv in dic) if (i % kv.Key != kv.Value)
            {
                flg = false;
                break;
            }
            if (flg)
            {
                WriteLine(i);
                return;
            }
        }
        WriteLine("NaN");

    }
    // 中国剰余定理
    // x == r[i] (mod m[i]) を満たすような
    // x == y (mod z) を返却する
    static (long y, long z) Calc(long[] r, long[] m)
    {
        var n = r.Length;
        var r0 = 0L;
        var m0 = 1L;
        for (var i = 0; i < n; ++i)
        {
            var r1 = _Mod(r[i], m[i]);
            var m1 = m[i];
            if (m0 < m1)
            {
                var tmp = r0; r0 = r1; r1 = tmp;
                tmp = m0; m0 = m1; m1 = tmp;
            }
            if (m0 % m1 == 0)
            {
                if (r0 % m1 != r1) return (0, 0);
                continue;
            }
            var (g, im) = _invGcd(m0, m1);
            var u1 = m1 / g;
            if ((r1 - r0) % g > 0) return (0, 0);
            var x = (r1 - r0) / g % u1 * im % u1;
            r0 += x * m0;
            m0 *= u1;
            if (r0 < 0) r0 += m0;
        }
        return (r0, m0);
    }
    static (long g, long x) _invGcd(long a, long b)
    {
        a = _Mod(a, b);
        if (a == 0) return (b, 0);
        var s = b;
        var t = a;
        var m0 = 0L;
        var m1 = 1L;
        while (t > 0)
        {
            var u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            var tmp = s; s = t; t = tmp;
            tmp = m0; m0 = m1; m1 = tmp;
        }
        if (m0 < 0) m0 += b / s;
        return (s, m0);
    }
    static long _Mod(long x, long m)
    {
        x %= m;
        if (x < 0) x += m;
        return x;
    }
}
0