結果

問題 No.186 中華風 (Easy)
ユーザー uwi
提出日時 2015-04-19 23:27:07
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 85 ms
コード長 4,266 Byte
コンパイル時間 2,972 ms
使用メモリ 19,232 KB
最終ジャッジ日時 2019-10-09 09:17:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 80 ms
19,228 KB
1.in AC 81 ms
19,228 KB
2.in AC 82 ms
19,232 KB
3.in AC 80 ms
19,228 KB
4.in AC 79 ms
19,232 KB
5.in AC 82 ms
19,228 KB
6.in AC 82 ms
19,228 KB
7.in AC 84 ms
19,228 KB
8.in AC 82 ms
19,232 KB
9.in AC 83 ms
19,228 KB
A.in AC 80 ms
18,528 KB
B.in AC 81 ms
19,232 KB
C.in AC 82 ms
19,232 KB
D.in AC 80 ms
19,228 KB
E.in AC 83 ms
19,232 KB
F.in AC 82 ms
19,232 KB
G.in AC 84 ms
19,228 KB
system_test1.txt AC 85 ms
19,232 KB
system_test2.txt AC 83 ms
19,228 KB
system_test3.txt AC 82 ms
19,228 KB
system_test4.txt AC 81 ms
19,228 KB
system_test5.txt AC 81 ms
19,228 KB
テストケース一括ダウンロード

ソースコード

diff #
package contest;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Q447 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		long x1 = ni(), y1 = ni();
		long x2 = ni(), y2 = ni();
		long x3 = ni(), y3 = ni();
		
		long x12 = crt(y1, x1, y2, x2);
		if(x12 == -1){
			out.println(-1);
			return;
		}
		long y12 = y1/gcd(y1,y2)*y2;
		
		long ret = crt(y12, x12, y3, x3);
		if(ret == -1){
			out.println(-1);
			return;
		}
		long y123 = y12/gcd(y12,y3)*y3;
		if(ret == 0)ret += y123;
		out.println(ret);
	}
	
	public static long gcd(long a, long b) {
		while (b > 0) {
			long c = a;
			a = b;
			b = c % b;
		}
		return a;
	}
	
	
	public static long crt(long p, long m, long q, long n)
	{
		long[] apr = exgcd(p, q);
		if((n - m) % apr[0] != 0)return -1;
		long mod = p * (q / apr[0]);
		long a = (mul(mul(apr[1], (n-m)/apr[0], mod), p, mod) + m) % mod;
		if(a < 0)a += mod;
		return a;
	}
	
	public static long[] exgcd(long a, long b)
	{
		if(a == 0 || b == 0)return null;
		int as = Long.signum(a);
		int bs = Long.signum(b);
		a = Math.abs(a); b = Math.abs(b);
		long p = 1, q = 0, r = 0, s = 1;
		while(b > 0){
			long c = a / b;
			long d;
			d = a; a = b; b = d % b;
			d = p; p = q; q = d - c * q;
			d = r; r = s; s = d - c * s;
		}
		return new long[]{a, p * as, r * bs};
	}

	
	public static long mul(long a, long b, long mod)
	{
		a %= mod; if(a < 0)a += mod;
		b %= mod; if(b < 0)b += mod;
		long ret = 0;
		int x = 63-Long.numberOfLeadingZeros(b);
		for(;x >= 0;x--){
			ret += ret;
			if(ret >= mod)ret -= mod;
			if(b<<~x<0){
				ret += a;
				if(ret >= mod)ret -= mod;
			}
		}
		return ret;
	}


	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new Q447().run(); }
	
	private byte[] inbuf = new byte[1024];
	private int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0