結果
問題 | No.229 線分上を往復する3つの動点の一致 |
ユーザー |
![]() |
提出日時 | 2015-06-19 23:18:37 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 177 ms / 5,000 ms |
コード長 | 3,594 bytes |
コンパイル時間 | 2,556 ms |
コンパイル使用メモリ | 80,028 KB |
実行使用メモリ | 42,812 KB |
最終ジャッジ日時 | 2024-07-07 04:16:50 |
合計ジャッジ時間 | 11,613 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
package no229; import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Frac[] t = new Frac[3]; for(int i=0;i<3;i++) { t[i] = new Frac(2, sc.nextInt()); } Frac ans = new Frac(Long.MAX_VALUE); for(int i=0;i<8;i++) { Frac[] s = new Frac[3]; for(int j=0;j<3;j++) { s[j] = ((i >> j & 1 ) == 0) ? t[j] : t[j].multiply(new Frac(-1)); } Frac x = s[0].subtract(s[1]).abs().inverse().lcm(s[1].subtract(s[2]).abs().inverse()).multiply(new Frac(2)); ans = ans.min(x); } System.out.println(ans); } } class Frac { public static Frac ZERO = new Frac(0,1); BigInteger a,b; public Frac(long a) { this.a = BigInteger.valueOf(a); this.b = BigInteger.ONE; } public Frac(long a,long b) { this(BigInteger.valueOf(a),BigInteger.valueOf(b)); } public Frac(BigInteger a,BigInteger b) { int sign = a.signum() * b.signum(); a = a.abs(); b = b.abs(); BigInteger gcd = a.gcd(b); this.a = a.divide(gcd); this.b = b.divide(gcd); if (sign < 0) { this.a = this.a.negate(); } } public Frac add(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b).add(x.b.multiply(y.a)), x.b.multiply(y.b)); } public Frac subtract(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b).subtract(x.b.multiply(y.a)), x.b.multiply(y.b)); } public Frac multiply(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.a),x.b.multiply(y.b)); } public Frac divide(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b),x.b.multiply(y.a)); } public long longValueExact() { if (!b.equals(BigInteger.ONE)) { throw new ArithmeticException(); } return a.longValueExact(); } public boolean equals(Object o) { if (o instanceof Frac) { Frac f = (Frac) o; return this.a.equals(f.a) && this.b.equals(f.b); } return super.equals(o); } public int hashCode() { return a.hashCode() ^ b.hashCode(); } public String toString() { return a + "/" + b; } public Frac lcm(Frac y) { return new Frac(lcm(a.multiply(y.b),b.multiply(y.a)),b.multiply(y.b)); } private static BigInteger lcm(BigInteger a,BigInteger b) { return a.divide(a.gcd(b)).multiply(b); } public Frac abs() { return new Frac(a.abs(), b); } public Frac inverse() { return new Frac(b,a); } public Frac min(Frac y) { if (a.multiply(y.b).compareTo(y.a.multiply(b)) < 0) { return this; }else{ return y; } } } class Mod { public static long n(long x,long mod) { x %= mod; if (x < 0) { x += mod; } return x; } public static long pow(long a,long n,long mod) { long res = 1; while(n > 0) { if ((n & 1) > 0) { res = (res * a) % mod; } a = (a * a) % mod; n/=2; } return res; } 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; } /** * @return [a,m] where x = a (mod m) */ 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; } }