結果

問題 No.3179 3 time mod
コンテスト
ユーザー ks2m
提出日時 2025-06-13 21:39:36
言語 Java
(openjdk 23)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,010 bytes
コンパイル時間 3,165 ms
コンパイル使用メモリ 88,308 KB
実行使用メモリ 46,796 KB
最終ジャッジ日時 2025-06-14 01:39:48
合計ジャッジ時間 9,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long[] m = new long[3];
		for (int i = 0; i < 3; i++) {
			m[i] = sc.nextLong();
		}
		long[] r = new long[3];
		for (int i = 0; i < 3; i++) {
			r[i] = sc.nextLong();
		}
		sc.close();

		long[] res = crt(r, m);
		if (res[1] == 0) {
			System.out.println(0);
		} else {
			long lcm = lcm(lcm(m[0], m[1]), m[2]);
			long ans = (n - res[0] + lcm) / lcm;
			System.out.println(ans);
		}
	}

	static long[] crt(long[] r, long[] m) {
		assert r.length == m.length : "|r|=" + r.length + ", |m|=" + m.length;

		int n = r.length;
		long r0 = 0, m0 = 1;
		for (int i = 0; i < n; i++) {
			assert 1 <= m[i] : "m[" + i + "]=" + m;

			long r1 = r[i] % m[i];
			if (r1 < 0) {
				r1 += m[i];
			}
			long m1 = m[i];
			if (m0 < m1) {
				long tmp = r0;
				r0 = r1;
				r1 = tmp;
				tmp = m0;
				m0 = m1;
				m1 = tmp;
			}
			if (m0 % m1 == 0) {
				if (r0 % m1 != r1) {
					return new long[] { 0, 0 };
				}
				continue;
			}

			long[] ig = invGcd(m0, m1);
			long g = ig[0], im = ig[1];
			long u1 = m1 / g;
			if ((r1 - r0) % g != 0) {
				return new long[] { 0, 0 };
			}

			long x = (r1 - r0) / g % u1 * im % u1;
			r0 += x * m0;
			m0 *= u1;
			if (r0 < 0) {
				r0 += m0;
			}
		}
		return new long[] { r0, m0 };
	}

	private static long[] invGcd(long a, long b) {
		a = a % b;
		if (a < 0) {
			a += b;
		}
		if (a == 0) {
			return new long[] { b, 0 };
		}

		long s = b, t = a;
		long m0 = 0, m1 = 1;
		while (t > 0) {
			long u = s / t;
			s -= t * u;
			m0 -= m1 * u;
			long tmp = s;
			s = t;
			t = tmp;
			tmp = m0;
			m0 = m1;
			m1 = tmp;
		}
		if (m0 < 0) {
			m0 += b / s;
		}
		return new long[] { s, m0 };
	}

	static long lcm(long a, long b) {
		BigInteger ba = BigInteger.valueOf(a);
		BigInteger bb = BigInteger.valueOf(b);
		return ba.multiply(bb).divide(ba.gcd(bb)).longValue();
	}
}
0