結果
問題 | 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 mathn = 2 * 10**5 + 10pf = [0] * nfor i in range(n):pf[i] = ifor i in range(2, n):if pf[i] == i:j = 2 * iwhile j < n:pf[j] = ij = j + i# print(pf)phi = [1] * nfor i in range(2, n):x = ipp = -1while x > 1:p = pf[x]if p == pp:phi[i] *= pelse:phi[i] *= p - 1pp = px //= 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 -= 1res = 0sqrtR = int(math.sqrt(l + r))for i in range(2, sqrtR + 1):if l // i != r // i:res += phi[i]i1 = 0i2 = 1q_prv = rwhile 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_maxif ql >= qr:i1 += 1else:i2 += 1print(res)