結果

問題 No.186 中華風 (Easy)
ユーザー GrenacheGrenache
提出日時 2016-06-21 22:14:23
言語 Java21
(openjdk 21)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 2,735 bytes
コンパイル時間 3,680 ms
コンパイル使用メモリ 77,904 KB
実行使用メモリ 41,580 KB
最終ジャッジ日時 2024-07-19 18:28:00
合計ジャッジ時間 7,660 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
41,312 KB
testcase_01 AC 136 ms
41,580 KB
testcase_02 AC 131 ms
41,292 KB
testcase_03 AC 131 ms
41,544 KB
testcase_04 AC 132 ms
41,320 KB
testcase_05 AC 129 ms
41,240 KB
testcase_06 AC 117 ms
40,372 KB
testcase_07 AC 134 ms
41,308 KB
testcase_08 AC 117 ms
40,384 KB
testcase_09 AC 132 ms
41,188 KB
testcase_10 AC 130 ms
41,360 KB
testcase_11 AC 130 ms
41,320 KB
testcase_12 AC 131 ms
41,244 KB
testcase_13 AC 131 ms
41,152 KB
testcase_14 AC 129 ms
41,356 KB
testcase_15 AC 133 ms
41,176 KB
testcase_16 AC 132 ms
41,288 KB
testcase_17 AC 132 ms
41,132 KB
testcase_18 AC 136 ms
41,444 KB
testcase_19 AC 117 ms
40,004 KB
testcase_20 AC 132 ms
41,208 KB
testcase_21 AC 131 ms
41,216 KB
testcase_22 AC 130 ms
41,252 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.*;
import java.util.Scanner;


public class Main_yukicoder186 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long x1 = sc.nextInt();
        long y1 = sc.nextInt();
        long x2 = sc.nextInt();
        long y2 = sc.nextInt();
        long x3 = sc.nextInt();
        long y3 = sc.nextInt();

//        System.out.printf("%d %d\n", crt(x1, y1, x2, y2), lcm(y1, y2));
        long ret = crt(x1, y1, x2, y2);

        if (ret != -1) {
        	ret = crt(ret, lcm(y1, y2), x3, y3);
        }

        if (ret == 0) {
        	ret = lcm(lcm(y1, y2), y3);
        }

        System.out.println(ret);

        sc.close();
    }

	private static long crt(long a1, long n1, long a2, long n2) {
		long[] xy = new long[2];
		long d = extgcd(n1, n2, xy);
		long lcm = n1 / d * n2;

		BigInteger blcm = BigInteger.valueOf(lcm);

		if (d == 1) {
			BigInteger tmp = BigInteger.valueOf(a1).multiply(BigInteger.valueOf(n2)).mod(blcm).multiply(BigInteger.valueOf(xy[1])).mod(blcm);
			tmp = tmp.add(BigInteger.valueOf(a2).multiply(BigInteger.valueOf(n1)).mod(blcm).multiply(BigInteger.valueOf(xy[0])).mod(blcm));
			tmp = tmp.mod(blcm).add(blcm).mod(blcm);

//			long tmp = (a1 * n2 % lcm) * xy[1] % lcm + (a2 * n1 % lcm) * xy[0] % lcm;
//			tmp = (tmp % lcm + lcm) % lcm;

			return tmp.longValue();
		} else if ((a1 - a2) % d == 0) {
			BigInteger x = BigInteger.valueOf(xy[0]).multiply(BigInteger.valueOf(a2 - a1)).divide(BigInteger.valueOf(d)).mod(blcm);
			BigInteger y = BigInteger.valueOf(xy[1]).multiply(BigInteger.valueOf(a2 - a1)).divide(BigInteger.valueOf(d)).mod(blcm);
			BigInteger tmp1 = BigInteger.valueOf(n1).multiply(x).add(BigInteger.valueOf(a1)).mod(blcm).add(blcm).mod(blcm);
			BigInteger tmp2 = BigInteger.valueOf(-n2).multiply(y).add(BigInteger.valueOf(a2)).mod(blcm).add(blcm).mod(blcm);
//			long x = xy[0] * (a2 - a1) / d % lcm;
//			long y = xy[1] * (a2 - a1) / d % lcm;
//			long tmp1 = ((n1 * x + a1) % lcm + lcm) % lcm;
//			long tmp2 = ((a2 - n2 * y) % lcm + lcm ) % lcm;
			if (tmp1.compareTo(tmp2) != 0 || tmp1.compareTo(BigInteger.ZERO) < 0 || tmp2.compareTo(BigInteger.ZERO) < 0) {
//			if (tmp1 != tmp2 || tmp1 < 0 || tmp2 < 0) {
				System.err.println("err");
//				System.err.printf("%d %d\n", tmp1, tmp2);
			}
			return tmp1.longValue();
		} else {
			return -1;
		}
	}

	private static long extgcd(long n, long m, long[] xy) {
		if (m == 0) {
			xy[0] = 1;
			xy[1] = 0;

			return n;
		} else {
			long ret = extgcd(m, n % m, xy);

			long tmp = xy[1];
			xy[1] = xy[0] - n / m * tmp;
			xy[0] = tmp;

			return ret;
		}
	}

	private static long lcm(long n, long m) {
		long[] xy = new long[2];
		return n / extgcd(n, m, xy) * m;
	}
}
0