結果

問題 No.3179 3 time mod
ユーザー kakel-san
提出日時 2025-06-13 22:41:44
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 1,951 bytes
コンパイル時間 8,388 ms
コンパイル使用メモリ 168,616 KB
実行使用メモリ 188,760 KB
最終ジャッジ日時 2025-06-14 01:43:22
合計ジャッジ時間 12,389 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (109 ミリ秒)。
  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 static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static long NN => long.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var k = NList;
        var m = NList;
        var ans = Calc(m, k);
        WriteLine(n / ans.z + (n % ans.z >= ans.y ? 1 : 0));
    }
    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