結果

問題 No.2119 一般化百五減算
ユーザー 👑 kakel-sankakel-san
提出日時 2022-11-04 22:38:53
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 2,855 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 67,872 KB
実行使用メモリ 27,856 KB
最終ジャッジ日時 2023-09-26 01:08:21
合計ジャッジ時間 5,094 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
21,600 KB
testcase_01 AC 60 ms
21,548 KB
testcase_02 AC 62 ms
23,580 KB
testcase_03 AC 61 ms
19,412 KB
testcase_04 AC 63 ms
21,516 KB
testcase_05 AC 61 ms
21,452 KB
testcase_06 AC 62 ms
23,588 KB
testcase_07 AC 65 ms
23,620 KB
testcase_08 AC 63 ms
21,568 KB
testcase_09 AC 63 ms
21,484 KB
testcase_10 AC 63 ms
23,668 KB
testcase_11 AC 66 ms
23,596 KB
testcase_12 AC 64 ms
21,456 KB
testcase_13 AC 64 ms
23,516 KB
testcase_14 AC 62 ms
21,492 KB
testcase_15 AC 63 ms
23,696 KB
testcase_16 AC 63 ms
21,496 KB
testcase_17 AC 64 ms
21,512 KB
testcase_18 AC 64 ms
21,444 KB
testcase_19 AC 64 ms
21,648 KB
testcase_20 AC 140 ms
27,560 KB
testcase_21 AC 63 ms
21,596 KB
testcase_22 AC 167 ms
25,556 KB
testcase_23 AC 164 ms
25,704 KB
testcase_24 AC 175 ms
27,856 KB
権限があれば一括ダウンロードができます

ソースコード

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