#1161527 (C#) No.3516 Very Large Range Mod

• 問題: No.3516 Very Large Range Mod
• ユーザー: kakel-san
• 提出日時: 2026-04-24 23:53:41
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 335 ms / 2,000 ms
• コード長: 4,261 bytes
• コンパイル時間: 11,034 ms
• コンパイル使用メモリ: 173,400 KB
• 実行使用メモリ: 228,852 KB
• 最終ジャッジ日時: 2026-04-24 23:54:06
• 合計ジャッジ時間: 22,916 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge4_1

ファイルパターン	結果
sample	AC * 3
other	AC * 30

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (91 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Runtime.Intrinsics.Arm;
using System.Runtime.Serialization;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (n, k, m) = (c[0], c[1], c[2]);
        var clist = NList;
        var vlist = NList;
        WriteLine(Large(n, k, m, clist, vlist));
    }
    static long Large(int n, int k, int m, int[] clist, int[] vlist)
    {
        if (m == 1)
        {
            var allcount = 0L;
            foreach (var ci in clist) allcount += ci;
            return allcount - k + 1;
        }
        var bi = 0;
        var bj = 0;
        var ei = 0;
        var ej = 0;
        var sum = 0L;
        {
            var tmp = k;
            while (tmp > 0)
            {
                var add = Math.Min(tmp, clist[ei] - ej);
                ej += add;
                tmp -= add;
                sum += (long)vlist[ei] * add;
                if (ej == clist[ei])
                {
                    ++ei;
                    ej = 0;
                }
            }
        }
        sum %= m;
        var ans = 0L;
        while (ei < n)
        {
            var maxx = Math.Min(clist[bi] - bj, clist[ei] - ej);
            var a = (vlist[ei] % m - vlist[bi] % m + m) % m;
            var b = (int)(m - sum) % m;
            int minx = -1, loopsize = 1;
            if (a == 0)
            {
                if (b == 0)
                {
                    minx = 0;
                }
            }
            else
            {
                minx = ExEuclid.SolveContract(a, b, m);
                loopsize = m / (int)ExEuclid.GCD(m, a);
            }
            if (minx >= 0 && minx < maxx) ans += (maxx - 1 - minx) / loopsize + 1;
            sum = (sum + (long)maxx * a) % m;
            bj += maxx;
            if (bj == clist[bi])
            {
                ++bi;
                bj = 0;
            }
            ej += maxx;
            if (ej == clist[ei])
            {
                ++ei;
                ej = 0;
            }
        }
        if (sum == 0) ++ans;
        return ans;
    }
    class ExEuclid
    {
        // ユークリッド互除法により最大公約数を求める
        public static long GCD(long a, long b)
        {
            if (a < b) return GCD(b, a);
            if (a % b == 0) return b;
            else return GCD(b, a % b);
        }
        // 最小公倍数を求める
        public static long LCM(long a, long b)
        {
            var gcd = GCD(a, b);
            return a / gcd * b;
        }
        // 拡張ユークリッド互除法 ax + by = gcd(a, b) を満たす x, y を求める
        public static (long g, long x, long y) XGcd(long a, long b)
        {
            long x0 = 1, y0 = 0, x1 = 0, y1 = 1;
            while (b != 0)
            {
                var q = a / b;
                var prevA = a;
                a = b;
                b = prevA % b;
                var prevX0 = x0;
                var prevY0 = y0;
                x0 = x1;
                x1 = prevX0 - q * x1;
                y0 = y1;
                y1 = prevY0 - q * y1;
            }
            return (a, x0, y0);
        }
        // a ^ -1 mod m を求める
        static int ModInv(int a, int mod)
        {
            var (_, x, _) = XGcd(a, mod);
            return (int)((x + mod) % mod);
        }
        // ax === b (mod m) を満たすxを求める
        // 存在しない場合-1を返す
        public static int SolveContract(int a, int b, int m)
        {
            if (a == 0 || b == 0)
            {
                return 0;
            }
            var g = (int)GCD(a, m);
            if (b % g != 0) return -1;
            return (int)((long)b / g * ModInv(a / g, m / g) % (m / g));
        }
    }
}