結果

問題 No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...
ユーザー ks2mks2m
提出日時 2021-01-22 22:58:29
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,579 bytes
コンパイル時間 2,263 ms
コンパイル使用メモリ 86,748 KB
実行使用メモリ 47,716 KB
最終ジャッジ日時 2024-06-08 17:06:56
合計ジャッジ時間 6,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
47,716 KB
testcase_01 AC 49 ms
37,368 KB
testcase_02 AC 46 ms
37,200 KB
testcase_03 AC 47 ms
36,960 KB
testcase_04 AC 48 ms
37,216 KB
testcase_05 AC 52 ms
37,180 KB
testcase_06 AC 126 ms
44,128 KB
testcase_07 AC 132 ms
44,144 KB
testcase_08 AC 133 ms
43,964 KB
testcase_09 AC 112 ms
42,596 KB
testcase_10 AC 111 ms
42,732 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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());
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < t; i++) {
			String[] sa = br.readLine().split(" ");
			long[] a = new long[3];
			for (int j = 0; j < 3; j++) {
				a[j] = Long.parseLong(sa[j]);
			}
			long y = Long.parseLong(sa[3]);

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

	/**
	 * <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