結果

問題 No.186 中華風 (Easy)
ユーザー ぴろず
提出日時 2015-04-19 23:39:35
言語 Java11
(openjdk 11.0.5)
結果
AC  
実行時間 124 ms
コード長 1,381 Byte
コンパイル時間 2,176 ms
使用メモリ 34,140 KB
最終ジャッジ日時 2019-12-30 20:49:01

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 120 ms
33,864 KB
1.in AC 120 ms
33,900 KB
2.in AC 120 ms
33,804 KB
3.in AC 116 ms
33,800 KB
4.in AC 120 ms
33,952 KB
5.in AC 120 ms
34,140 KB
6.in AC 120 ms
34,132 KB
7.in AC 120 ms
33,752 KB
8.in AC 124 ms
33,812 KB
9.in AC 124 ms
33,752 KB
A.in AC 120 ms
33,920 KB
B.in AC 120 ms
33,964 KB
C.in AC 124 ms
33,996 KB
D.in AC 120 ms
33,880 KB
E.in AC 120 ms
33,988 KB
F.in AC 124 ms
34,084 KB
G.in AC 116 ms
33,752 KB
system_test1.txt AC 116 ms
33,776 KB
system_test2.txt AC 120 ms
33,896 KB
system_test3.txt AC 120 ms
34,072 KB
system_test4.txt AC 124 ms
33,848 KB
system_test5.txt AC 120 ms
33,896 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