#769335 (C#(csc)) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: 明智重蔵
• 提出日時: 2022-06-10 21:19:01
• 言語: C#(csc) (csc 3.9.0)
• 結果: WA
• 実行時間: -
• コード長: 4,531 bytes
• コンパイル時間: 1,212 ms
• コンパイル使用メモリ: 112,224 KB
• 実行使用メモリ: 29,444 KB
• 最終ジャッジ日時: 2024-09-21 05:51:07
• 合計ジャッジ時間: 2,766 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 21 WA * 2

コンパイルメッセージ

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.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(DivList, ModList);
        var Result = CRT.ChineseRem(ModList, DivList);
        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 };
    }
}