結果
問題 | No.2849 Birthday Donuts |
ユーザー |
|
提出日時 | 2024-06-11 23:42:26 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,149 bytes |
コンパイル時間 | 153 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 82,296 KB |
最終ジャッジ日時 | 2024-07-01 01:43:53 |
合計ジャッジ時間 | 5,715 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 1 |
other | AC * 1 WA * 1 RE * 19 |
ソースコード
import math n = 2 * 10**5 + 10 pf = [0] * n for i in range(n): pf[i] = i for i in range(2, n): if pf[i] == i: j = 2 * i while j < n: pf[j] = i j = j + i # print(pf) phi = [1] * n for i in range(2, n): x = i pp = -1 while x > 1: p = pf[x] if p == pp: phi[i] *= p else: phi[i] *= p - 1 pp = p x //= p # print(phi) acc = [0] * (n + 1) for i in range(2, n): acc[i] = acc[i - 1] + phi[i] T = int(input()) for t in range(T): l, r = map(int, input().split()) l -= 1 res = 0 sqrtR = int(math.sqrt(l + r)) for i in range(2, sqrtR + 1): if l // i != r // i: res += phi[i] i1 = 0 i2 = 1 q_prv = r while q_prv > sqrtR: ql = l // (i1 + 1) qr = r // (i2 + 1) q_max = max(ql, qr) if i1 != i2: res += acc[q_prv] - acc[max(q_max, sqrtR)] # print(i1, i2, max(q_max, sqrtR), q_prv) q_prv = q_max if ql >= qr: i1 += 1 else: i2 += 1 print(res)