結果
問題 | No.186 中華風 (Easy) |
ユーザー | toyuzuko |
提出日時 | 2020-09-20 19:23:25 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,471 bytes |
コンパイル時間 | 103 ms |
コンパイル使用メモリ | 10,868 KB |
実行使用メモリ | 8,148 KB |
最終ジャッジ日時 | 2023-09-06 16:29:53 |
合計ジャッジ時間 | 1,434 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
8,064 KB |
testcase_01 | AC | 16 ms
8,048 KB |
testcase_02 | AC | 15 ms
8,080 KB |
testcase_03 | AC | 15 ms
8,064 KB |
testcase_04 | AC | 15 ms
8,068 KB |
testcase_05 | AC | 15 ms
8,016 KB |
testcase_06 | AC | 15 ms
8,084 KB |
testcase_07 | AC | 15 ms
8,052 KB |
testcase_08 | AC | 14 ms
8,112 KB |
testcase_09 | AC | 15 ms
8,060 KB |
testcase_10 | AC | 15 ms
8,040 KB |
testcase_11 | AC | 14 ms
8,092 KB |
testcase_12 | AC | 15 ms
8,148 KB |
testcase_13 | AC | 15 ms
7,984 KB |
testcase_14 | AC | 15 ms
8,012 KB |
testcase_15 | AC | 15 ms
8,064 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 15 ms
8,048 KB |
testcase_19 | AC | 15 ms
8,064 KB |
testcase_20 | AC | 15 ms
8,040 KB |
testcase_21 | AC | 15 ms
8,052 KB |
testcase_22 | AC | 15 ms
8,004 KB |
ソースコード
def floor_sum(n, m, a, b): res = 0 while True: if a >= m: res += (n - 1) * n * (a // m) // 2 a %= m if b >= m: res += n * (b // m) b %= m y_max = (a * n + b) // m if y_max == 0: break x_max = b - y_max * m res += (n + x_max // a) * y_max n, m, a, b = y_max, a, m, x_max % a return res def inv_gcd(a, b): a %= b if a == 0: return b, 0 s = b t = a m0 = 0 m1 = 1 while t: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += b // s return s, m0 def inv_mod(x, m): assert 1 <= m g, im = inv_gcd(x, m) assert g == 1 return im def crt(r, m): assert len(r) == len(m) n = len(r) r0 = 0 m0 = 1 for i in range(n): assert 1 <= m[i] r1 = r[i] % m[i] m1 = m[i] if m0 < m1: r0, r1 = r1, r0 m0, m1 = m1, m0 if m0 % m1 == 0: if r0 % m1 != r1: return 0, 0 continue g, im = inv_gcd(m0, m1) u1 = m1 // g if (r1 - r0) % g: return 0, 0 x = (r1 - r0) // g * im % u1 r0 += x * m0 m0 *= u1 if (r0 < 0): r0 += m0 return r0, m0 R = [] M = [] for _ in range(3): r, m = map(int, input().split()) R.append(r) M.append(m) r, m = crt(R, M) if m == 0: print(-1) else: print(r)