結果
問題 | No.186 中華風 (Easy) |
ユーザー |
|
提出日時 | 2017-04-18 19:17:55 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 1,521 ms |
コンパイル使用メモリ | 174,740 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 18:46:21 |
合計ジャッジ時間 | 2,475 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(2999): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;import std.typecons; // Tuple, Nullable, BigFlagsimport std.numeric; // gcdimport std.bigint; // BigIntvoid main(){auto n = 3;auto xi = new BigInt[](n), yi = new BigInt[](n);foreach (ref x, ref y; lockstep(xi, yi)) {auto rd = readln.split.to!(BigInt[]);x = rd[0]; y = rd[1];}auto r1 = calc(xi[0], yi[0], xi[1], yi[1]), z1 = r1[0], l1 = r1[1];if (l1 == -1) {writeln(-1);return;}auto r2 = calc(z1, l1, xi[2], yi[2]), z2 = r2[0], l2 = r2[1];if (l2 == -1) {writeln(-1);return;}writeln(z2 == 0 ? l2 : z2);}auto calc(BigInt x1, BigInt y1, BigInt x2, BigInt y2){auto g = gcd(y1.to!long, y2.to!long);if (x1 % g != x2 % g) return Tuple!(BigInt, BigInt)(BigInt(-1), BigInt(-1));BigInt m, n;exEuclid(y1, y2, m, n);m *= (x2 - x1) / g;auto l = y1 / g * y2;return Tuple!(BigInt, BigInt)(((m * y1 + x1) % l + l) % l, l);}pure T exEuclid(T)(T a, T b, ref T x, ref T y){auto g = a;x = 1;y = 0;if (b != 0) {g = exEuclid(b, a % b, y, x);y -= a / b * x;}return g;}