結果
問題 | No.2882 Comeback |
ユーザー | LyricalMaestro |
提出日時 | 2024-10-01 02:00:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 221 ms / 2,000 ms |
コード長 | 2,611 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 108,544 KB |
最終ジャッジ日時 | 2024-10-01 02:00:23 |
合計ジャッジ時間 | 5,196 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
54,528 KB |
testcase_01 | AC | 40 ms
54,528 KB |
testcase_02 | AC | 40 ms
54,656 KB |
testcase_03 | AC | 41 ms
54,656 KB |
testcase_04 | AC | 39 ms
54,656 KB |
testcase_05 | AC | 84 ms
76,544 KB |
testcase_06 | AC | 95 ms
76,616 KB |
testcase_07 | AC | 99 ms
76,700 KB |
testcase_08 | AC | 90 ms
76,716 KB |
testcase_09 | AC | 95 ms
76,712 KB |
testcase_10 | AC | 221 ms
100,116 KB |
testcase_11 | AC | 185 ms
96,192 KB |
testcase_12 | AC | 195 ms
98,888 KB |
testcase_13 | AC | 205 ms
99,712 KB |
testcase_14 | AC | 172 ms
90,368 KB |
testcase_15 | AC | 191 ms
94,808 KB |
testcase_16 | AC | 212 ms
98,176 KB |
testcase_17 | AC | 173 ms
94,348 KB |
testcase_18 | AC | 207 ms
96,808 KB |
testcase_19 | AC | 188 ms
92,260 KB |
testcase_20 | AC | 184 ms
101,940 KB |
testcase_21 | AC | 189 ms
108,544 KB |
testcase_22 | AC | 204 ms
101,152 KB |
testcase_23 | AC | 185 ms
104,012 KB |
testcase_24 | AC | 146 ms
94,080 KB |
testcase_25 | AC | 42 ms
54,144 KB |
testcase_26 | AC | 40 ms
54,528 KB |
testcase_27 | AC | 42 ms
54,400 KB |
testcase_28 | AC | 39 ms
54,728 KB |
testcase_29 | AC | 40 ms
54,912 KB |
testcase_30 | AC | 107 ms
82,176 KB |
ソースコード
## https://yukicoder.me/problems/no/2882 import math from collections import deque def solve(A, B): sqrt_b = int(math.sqrt(B)) answer1 = 0 for m in range(1, sqrt_b + 1): mod_a = A % m mod_b = B % m if mod_a >= mod_b: answer1 += 1 a_array = deque() # 半開区間の列を構築 for q in range(sqrt_b + 1): if q == 0: a_array.append((B, 0, A)) else: s = A // q if s > sqrt_b: a_array.append((s, q, A % q)) else: a_array.append((sqrt_b, -1, -1)) b_array = deque() for q in range(1, sqrt_b + 1): s = B // q if s > sqrt_b: b_array.append((s, q, B % q)) else: b_array.append((sqrt_b, -1, -1)) if b_array[-1][0] > sqrt_b: b_array.append((sqrt_b, -1, -1)) a = a_array.popleft() b = b_array.popleft() max_x = a[0] answer2 = 0 while len(a_array) > 0 and len(b_array) > 0: x = max(a_array[0][0], b_array[0][0]) ans = 0 a0, coef_a, intercept_a = a b0, coef_b, intercept_b = b if coef_a == coef_b: if intercept_b + coef_b * b0 <= intercept_a + coef_a * a0: ans += max_x - x else: # coef_a < coef_b: coef = coef_b - coef_a z = ((intercept_b + coef_b * b0 )- (intercept_a + coef_a * a0)) m_lower = z // coef + (1 if z % coef > 0 else 0) if m_lower <= x: ans += max_x - x elif x < m_lower <= max_x: ans += max_x - m_lower + 1 answer2 += ans if a_array[0][0] == b_array[0][0]: max_x = x a = a_array.popleft() b = b_array.popleft() elif a_array[0][0] > b_array[0][0]: max_x = x a = a_array.popleft() elif a_array[0][0] < b_array[0][0]: max_x = x b = b_array.popleft() return answer1 + answer2 def solve2(A, B): answer1 = 0 for m in range(1, B + 1): mod_a = A % m mod_b = B % m if mod_a >= mod_b: answer1 += 1 print(f"m = {m}") return answer1 def main(): T = int(input()) answers = [] for _ in range(T): A, B = map(int, input().split()) ans = solve(A, B) # ans2 = solve2(A, B) # print(ans2) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()