結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー Grenache
提出日時 2016-06-21 22:14:23
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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