結果
問題 | No.187 中華風 (Hard) |
ユーザー | uafr_cs |
提出日時 | 2016-02-18 22:12:24 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,607 bytes |
コンパイル時間 | 3,339 ms |
コンパイル使用メモリ | 77,612 KB |
実行使用メモリ | 60,540 KB |
最終ジャッジ日時 | 2023-10-23 18:14:48 |
合計ジャッジ時間 | 16,565 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 199 ms
60,056 KB |
testcase_01 | AC | 204 ms
59,924 KB |
testcase_02 | AC | 700 ms
60,276 KB |
testcase_03 | AC | 689 ms
60,332 KB |
testcase_04 | AC | 727 ms
60,180 KB |
testcase_05 | AC | 729 ms
60,144 KB |
testcase_06 | AC | 731 ms
60,240 KB |
testcase_07 | AC | 730 ms
60,180 KB |
testcase_08 | AC | 537 ms
60,392 KB |
testcase_09 | AC | 531 ms
60,336 KB |
testcase_10 | AC | 533 ms
60,276 KB |
testcase_11 | AC | 731 ms
60,112 KB |
testcase_12 | AC | 728 ms
58,332 KB |
testcase_13 | AC | 318 ms
60,172 KB |
testcase_14 | AC | 323 ms
60,500 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 125 ms
57,308 KB |
testcase_18 | AC | 200 ms
59,784 KB |
testcase_19 | AC | 113 ms
56,196 KB |
testcase_20 | AC | 605 ms
60,288 KB |
testcase_21 | AC | 127 ms
57,312 KB |
testcase_22 | AC | 728 ms
60,484 KB |
testcase_23 | AC | 129 ms
57,380 KB |
testcase_24 | AC | 127 ms
57,256 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; class Scratch { public static long mod_inv(long a, long m){ return (a == 1 ? 1 : (1 - m*mod_inv(m%a, a)) / a + m); } public static long gcd(long a, long b){ return b == 0 ? a : gcd(b, a % b); } public static boolean make_so(long[] as, long[] ms){ while(true) { boolean updated = false; for (int fst = 0; fst < ms.length; fst++) { for (int snd = fst + 1; snd < ms.length; snd++) { long gcd = gcd(ms[fst], ms[snd]); if (gcd == 1) { continue; } updated = true; if (as[fst] % gcd != as[snd] % gcd) { return false; } ms[fst] /= gcd; ms[snd] /= gcd; while (true) { long gt = gcd(ms[fst], gcd); if (gt == 1) { break; } ms[fst] *= gt; gcd /= gt; } ms[snd] *= gcd; as[fst] %= ms[fst]; as[snd] %= ms[snd]; } } if(!updated){ break; } } return true; } public static long chinese_remainder(long[] as, long[] ms){ long[] vs = new long[ms.length]; long[] sums = new long[ms.length]; long[] invs = new long[ms.length]; for(int i = 0; i < ms.length; i++){ invs[i] = 1; // mod(ms[i]) の中で 1 / (ms[0] * ms[1] ... ms[i - 1]) を求める sums[i] = as[i]; // mod(ms[i]) の中で, a[i] - v[0] - v[1]ms[0] ... を求める long mult = 1; // mod(ms[i]) の中で, ms[0] * ... * ms[i - 2] を求める for(int j = 0; j < i; j++){ sums[i] -= (vs[j] * mult) % ms[i]; if(sums[i] < 0){ sums[i] += ms[i]; } invs[i] = (invs[i] * mod_inv(ms[j], ms[i])) % ms[i]; mult = (mult * ms[j]) % ms[i]; } vs[i] = (sums[i] * invs[i]) % ms[i]; } long ret = 0; for(int i = 0; i < ms.length; i++){ long mult = 1; for(int j = 0; j < i; j++){ mult *= ms[j]; mult %= 1000000007;}// ここで MOD が必要な場合は取る ret += vs[i] * mult;// ここで MOD が必要な場合は取る ret %= 1000000007; } return ret; } public static void main(String[] args) { try (Scanner sc = new Scanner(System.in)) { final int N = sc.nextInt(); long[] as = new long[N]; long[] ms = new long[N]; for (int i = 0; i < N; i++){ as[i] = sc.nextLong(); ms[i] = sc.nextLong(); } final boolean so = make_so(as, ms); //System.out.println(Arrays.toString(as)); //System.out.println(Arrays.toString(ms)); if(!so){ System.out.println(-1); return; } long prod = 1; for(final long p : ms){ prod *= p; prod %= 1000000007; } final long ret = chinese_remainder(as, ms); System.out.println(ret); } } }