結果

問題 No.186 中華風 (Easy)
ユーザー 明智重蔵明智重蔵
提出日時 2022-06-10 21:48:57
言語 C#
(.NET 8.0.203)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,559 bytes
コンパイル時間 16,801 ms
コンパイル使用メモリ 157,836 KB
実行使用メモリ 177,416 KB
最終ジャッジ日時 2023-10-21 05:03:50
合計ジャッジ時間 10,841 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
32,492 KB
testcase_01 AC 81 ms
32,496 KB
testcase_02 AC 82 ms
32,500 KB
testcase_03 AC 84 ms
32,500 KB
testcase_04 AC 80 ms
32,496 KB
testcase_05 AC 83 ms
32,496 KB
testcase_06 AC 83 ms
32,496 KB
testcase_07 AC 83 ms
32,496 KB
testcase_08 AC 80 ms
32,496 KB
testcase_09 AC 80 ms
32,496 KB
testcase_10 AC 80 ms
32,496 KB
testcase_11 AC 80 ms
32,496 KB
testcase_12 AC 84 ms
32,500 KB
testcase_13 AC 81 ms
32,496 KB
testcase_14 AC 82 ms
32,500 KB
testcase_15 AC 82 ms
32,496 KB
testcase_16 AC 81 ms
32,496 KB
testcase_17 AC 81 ms
32,496 KB
testcase_18 AC 80 ms
32,496 KB
testcase_19 AC 81 ms
32,496 KB
testcase_20 AC 83 ms
32,496 KB
testcase_21 AC 84 ms
32,492 KB
testcase_22 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (106 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.0/publish/

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("10 20");
            WillReturn.Add("10 30");
            WillReturn.Add("10 40");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 20");
            WillReturn.Add("10 30");
            WillReturn.Add("30 40");
            //70
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 2");
            WillReturn.Add("0 4");
            WillReturn.Add("5 17");
            //-1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("80712 221549");
            WillReturn.Add("320302 699312");
            WillReturn.Add("140367 496729");
            //38774484298448350
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("0 539848");
            WillReturn.Add("0 760946");
            WillReturn.Add("0 118044");
            //6061488222537144
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("982056 991130");
            WillReturn.Add("624239 963840");
            WillReturn.Add("44170 383709");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var ModList = new List<long>();
        var DivList = new List<long>();

        SplitAct(InputList[0]);
        ModList.Add(wkArr[0]); DivList.Add(wkArr[1]);

        SplitAct(InputList[1]);
        ModList.Add(wkArr[0]); DivList.Add(wkArr[1]);

        SplitAct(InputList[2]);
        ModList.Add(wkArr[0]); DivList.Add(wkArr[1]);

        var Result = CRT.ChineseRem(ModList, DivList);
        if (Result.r == 0) {
            Console.WriteLine(Result.m);
        }
        else if (Result.m == -1) {
            Console.WriteLine(-1);
        }
        else {
            Console.WriteLine(Result.r);
        }
    }
}

// 中国剰余定理クラス
internal class CRT
{
    // 負の数にも対応した mod
    // 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
    // しかし単に -17 % 5 では -2 になってしまう
    static long mod(long a, long m)
    {
        return (a % m + m) % m;
    }

    // 拡張 Euclid の互除法
    // ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
    static long extGcd(long a, long b, ref long p, ref long q)
    {
        if (b == 0) { p = 1; q = 0; return a; }
        long d = extGcd(b, a % b, ref q, ref p);
        q -= a / b * p;
        return d;
    }

    internal struct CRT_Result_Def
    {
        internal long r;
        internal long m;
    }

    // 中国剰余定理 (2元の場合)
    // リターン値を (r, m) とすると解は x ≡ r (mod. m)
    // 解なしの場合は (0, -1) をリターン
    internal static CRT_Result_Def ChineseRem(long Div1, long Mod1, long Div2, long Mod2)
    {
        long p = 1, q = 0;
        long d = extGcd(Mod1, Mod2, ref p, ref q); // p is inv of m1/d (mod. m2/d)
        if ((Div2 - Div1) % d != 0) return new CRT_Result_Def() { r = 0, m = -1 };
        long m = Mod1 * (Mod2 / d); // lcm of (m1, m2)
        long tmp = (Div2 - Div1) / d * p % (Mod2 / d);
        long r = mod(Div1 + Mod1 * tmp, m);
        return new CRT_Result_Def() { r = r, m = m };
    }

    // 中国剰余定理 (n元の場合)
    // リターン値を (r, m) とすると解は x ≡ r (mod. m)
    // 解なしの場合は (0, -1) をリターン
    internal static CRT_Result_Def ChineseRem(List<long> b, List<long> m)
    {
        long r = 0, M = 1;
        for (int i = 0; i < b.Count; i++) {
            long p = 1, q = 0;
            long d = extGcd(M, m[i], ref p, ref q); // p is inv of M/d (mod. m[i]/d)
            if ((b[i] - r) % d != 0) {
                return new CRT_Result_Def() { r = 0, m = -1 };
            }
            long tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        return new CRT_Result_Def() { r = mod(r, M), m = M };
    }
}
0