結果
問題 | No.3022 一元一次式 mod 1000000000 |
ユーザー |
![]() |
提出日時 | 2025-02-14 22:30:20 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 905 bytes |
コンパイル時間 | 3,455 ms |
コンパイル使用メモリ | 95,080 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-17 12:57:20 |
合計ジャッジ時間 | 4,619 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import std.algorithm, std.array, std.bigint, std.conv, std.math, std.stdio, std.typecons, std.range; long gcd(long a, long b, ref long x, ref long y) { if (b == 0) { x = 1; y = 0; return a; } long d = gcd(b, a % b, y, x); y -= a / b * x; return d; } long solve(long N, long M) { if (M == 0) { long p2, p5; while (N % 2 == 0) { N /= 2; p2++; } while (N % 5 == 0) { N /= 5; p5++; } return 2L ^^ max(0, 9-p2) * 5L ^^ max(0, 9-p5); } long x, y; auto g = gcd(N, 10L^^9, x, y); if (M % g != 0) return -1; x *= -M/g; auto mod = 10L^^9 / g; if (x < 0) x = x%mod + mod; else x = x%mod; return x == 0 ? 1 : x; } void main() { auto t = readln[0 .. $-1].to!uint; long[] result; foreach (_; 0 .. t) { auto tmp = readln.split.to!(long[]); result ~= solve(tmp[0], tmp[1] % 10L^^9); } foreach (r; result) { writeln(r); } }