結果

問題 No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...
コンテスト
ユーザー ks2m
提出日時 2021-01-22 22:51:59
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,540 bytes
コンパイル時間 6,983 ms
コンパイル使用メモリ 84,552 KB
実行使用メモリ 89,332 KB
最終ジャッジ日時 2024-12-28 04:56:17
合計ジャッジ時間 21,448 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 WA * 1 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			String[] sa = br.readLine().split(" ");
			int[] a = new int[3];
			for (int j = 0; j < 3; j++) {
				a[j] = Integer.parseInt(sa[j]);
			}
			long y = Long.parseLong(sa[3]);

			Arrays.sort(a);
			long ans = 0;
			long e = y / a[2];
			for (long j = 0; j <= e; j++) {
				long z = y - a[2] * j;
				long[] c = crt(new long[] {z, 0}, new long[] {a[0], a[1]});
				if (c[1] > 0) {
					long x = z - c[0];
					if (x >= 0) {
						ans += x / c[1] + 1;
					}
				}
			}
			System.out.println(ans);
		}
		br.close();
	}

	/**
	 * <pre>
	 * 中国剰余定理
	 * x≡r[i] (mod m[i])を解く。
	 * O(n log lcm(m[i]))
	 * 
	 * ■制約
	 * |r|＝|m|
	 * 1≦m[i]
	 * lcm(m[i])がlongに収まる。
	 * 
	 * ■戻り値
	 * x≡y (mod z) となる{y, z} (0≦y＜z＝lcm(m[i]))
	 * 答えがない場合は{0, 0}
	 * n＝0の時は{0, 1}
	 * </pre>
	 * 
	 * https://atcoder.jp/contests/acl1/submissions/16949778
	 * https://atcoder.jp/contests/abc186/submissions/18908892
	 */
	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 };
	}
}
0