結果

問題 No.2849 Birthday Donuts
コンテスト
ユーザー AngrySadEight
提出日時 2024-06-11 01:35:57
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,450 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 85,436 KB
最終ジャッジ日時 2024-07-01 01:43:16
合計ジャッジ時間 7,434 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other AC * 1 WA * 1 RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def my_gcd(a, b):
    ret = 0
    if a < b:
        a, b = b, a
    if b == 0:
        ret = a
    else:
        ret = my_gcd(b, a % b)
    return ret

divisor = [-1 for _ in range(300002)]
for i in range(2, 300001):
    for j in range(2, 300000 // i + 1):
        divisor[j * i] = j

phi = [0 for _ in range(300002)]
for i in range(2, 300001):
    now = i
    div = -1
    tot = i
    while True:
        if divisor[now] == -1:
            if now != div:
                tot = tot * (now - 1)
                tot //= now
            break
        if div != divisor[now]:
            div = divisor[now]
            tot = tot * (div - 1)
            tot //= div
        now //= div
    phi[i] = tot

phi_sum = [0 for _ in range(300002)]
for i in range(2, 300001):
    phi_sum[i] = phi_sum[i - 1] + phi[i]

T = int(input())
for _ in range(T):
    L, R = map(int, input().split())
    ans = 0
    for i in range(2, 401):
        k1 = (L - 1) // i
        k2 = R // i
        if k1 < k2:
            ans += phi[i]
    left = 0
    right = 1
    prev = R
    while True:
        if R < 400:
            break
        nl = (L - 1) // (left + 1)
        nr = R // (right + 1)
        
        val = max(nl, nr)
        if left != right:
            ans += (phi_sum[prev] - phi_sum[max(val, 400)])
        if val <= 400:
            break
        prev = val
        if nl >= nr:
            left += 1
        else:
            right += 1
    print(ans)
0