結果

問題 No.816 Beautiful tuples
コンテスト
ユーザー kakel-san
提出日時 2026-06-14 22:20:56
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 73 ms / 1,500 ms
コード長 2,795 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,035 ms
コンパイル使用メモリ 173,512 KB
実行使用メモリ 197,216 KB
最終ジャッジ日時 2026-06-14 22:21:14
合計ジャッジ時間 13,805 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (124 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

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 (a, b) = (c[0], c[1]);
        var r = new long[] { ((a - b) % a + a) % a, ((b - a) % b + b) % b };
        var m = new long[] { a, b };
        var (y, z) = CRT.Calc(r, m);
        if (y < 0) y = (y % z + z) % z;
        while (y == 0 || y == a || y == b)
        {
            y += z;
        }
        if ((a + b) % y == 0)
        {
            WriteLine(y);
        }
        else
        {
            WriteLine(-1);
        }
    }
    // 中国剰余定理
    // x === r[0] (mod m[0]), x === r[1] (mod m[1]), x === r[2] (mod m[2]) ... を満たすような
    // x を、y (mod z) の形で返却する
    class CRT
    {
        public 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