結果

問題 No.186 中華風 (Easy)
ユーザー ぴろず
提出日時 2015-04-19 23:39:35
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 120 ms
コード長 1,381 Byte
コンパイル時間 1,524 ms
使用メモリ 21,400 KB
最終ジャッジ日時 2019-10-09 09:17:53

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 117 ms
21,392 KB
1.in AC 118 ms
21,400 KB
2.in AC 117 ms
21,396 KB
3.in AC 115 ms
21,232 KB
4.in AC 118 ms
21,396 KB
5.in AC 117 ms
21,168 KB
6.in AC 120 ms
21,200 KB
7.in AC 118 ms
21,396 KB
8.in AC 117 ms
21,292 KB
9.in AC 115 ms
21,200 KB
A.in AC 113 ms
21,196 KB
B.in AC 113 ms
21,168 KB
C.in AC 116 ms
21,396 KB
D.in AC 112 ms
21,168 KB
E.in AC 115 ms
21,160 KB
F.in AC 119 ms
21,396 KB
G.in AC 117 ms
21,164 KB
system_test1.txt AC 114 ms
21,164 KB
system_test2.txt AC 112 ms
21,228 KB
system_test3.txt AC 114 ms
21,232 KB
system_test4.txt AC 115 ms
21,164 KB
system_test5.txt AC 116 ms
21,232 KB
テストケース一括ダウンロード

ソースコード

diff #
package no186;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long[] a = new long[3];
		long[] b = new long[3];
		long[] m = new long[3];
		for(int i=0;i<3;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			a[i] = 1;
			b[i] = x;
			m[i] = y;
		}
		long[] x = Mod.linearCongruence(a, b, m);
		if (x == null) {
			System.out.println(-1);
		}else if(x[0] == 0) {
			if (x[1] > 0) {
				System.out.println(x[1]);
			}else{
				System.out.println(-1);
			}
		}else{
			System.out.println((x[0]%x[1]+x[1])%x[1]);
		}
	}
}
class Mod {
	public static long inverse(long a,long mod) {
		long b = mod, u = 1, v = 0;
		while(b > 0) {
			long temp;
			long t = a / b;
			a -= t * b;
			temp = a; a = b; b = temp;
			u -= t * v;
			temp = u; u = v; v = temp;
		}
		return (u % mod + mod) % mod;
	}
	public static long[] linearCongruence(long[] A,long[] B,long[] M) {
		long x = 0;
		long m = 1;
		for(int i=0;i<A.length;i++) {
			long a = A[i] * m;
			long b = B[i] - A[i] * x;
			long d = gcd(M[i],a);
			if (b % d != 0) {
				return null;
			}
			long t = b / d * inverse(a / d, M[i] / d) % (M[i] / d);
			x = x + m * t;
			m *= M[i] / d;
		}
		long[] ret = {x%m, m};
		return ret;
	}
	public static long gcd(long a,long b) {
		while(b!=0) {
			long r = a%b;
			a = b;
			b = r;
		}
		return a;
	}
}
0