結果

問題 No.2849 Birthday Donuts
ユーザー ecottea
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0