結果

問題 No.186 中華風 (Easy)
ユーザー 明智重蔵明智重蔵
提出日時 2022-06-10 21:15:07
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 4,798 bytes
コンパイル時間 16,016 ms
コンパイル使用メモリ 167,792 KB
実行使用メモリ 188,188 KB
最終ジャッジ日時 2024-09-21 05:51:04
合計ジャッジ時間 18,139 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
30,336 KB
testcase_01 AC 50 ms
29,824 KB
testcase_02 AC 51 ms
30,080 KB
testcase_03 AC 53 ms
30,080 KB
testcase_04 AC 51 ms
29,952 KB
testcase_05 AC 57 ms
30,208 KB
testcase_06 AC 54 ms
30,196 KB
testcase_07 AC 51 ms
30,080 KB
testcase_08 AC 51 ms
30,056 KB
testcase_09 AC 52 ms
30,080 KB
testcase_10 AC 52 ms
30,060 KB
testcase_11 AC 51 ms
30,056 KB
testcase_12 AC 51 ms
30,060 KB
testcase_13 AC 51 ms
30,208 KB
testcase_14 AC 52 ms
30,208 KB
testcase_15 AC 53 ms
30,336 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 53 ms
30,048 KB
testcase_19 AC 51 ms
30,060 KB
testcase_20 AC 50 ms
30,056 KB
testcase_21 AC 52 ms
30,464 KB
testcase_22 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (102 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.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 {
            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 };
    }
    /*
    // 中国剰余定理
    // リターン値を (r, m) とすると解は x ≡ r (mod. m)
    // 解なしの場合は (0, -1) をリターン
    pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) {
      long long r = 0, M = 1;
      for (int i = 0; i < (int)b.size(); ++i) {
        long long p, q;
        long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
        if ((b[i] - r) % d != 0) return make_pair(0, -1);
        long long tmp = (b[i] - r) / d * p % (m[i]/d);
        r += M * tmp;
        M *= m[i]/d;
      }
      return make_pair(mod(r, M), M);
    }
     * 
     * */

}
0