結果
問題 | No.2262 Fractions |
ユーザー |
![]() |
提出日時 | 2023-04-07 22:08:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 576 ms / 2,000 ms |
コード長 | 1,188 bytes |
コンパイル時間 | 535 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 116,252 KB |
最終ジャッジ日時 | 2024-11-27 02:06:08 |
合計ジャッジ時間 | 23,819 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
import sysinput = sys.stdin.readlineM = 3*10**5prime = [True] * (M+1)totient = list(range(M+1))for i in range(2, M+1):if prime[i]:for j in range(i, M+1, i):if j != i:prime[j] = Falsetotient[j] = totient[j]//i*(i-1)def solve(N, K):total = 0for n in range(1, N+1):total += totient[n]if K >= 2*total:print(-1)returnflip = Falseif K > total:K = 2*total-Kflip = TrueD = 10**12lb, ub = 0, D+1while ub-lb > 1:m = (lb+ub)//2cnt = 0g = [0]*(N+1)for i in range(1, N+1):g[i] = i*m//Dfor p in range(2, N+1):if not prime[p]:continuefor k in range(1, N//p+1)[::-1]:g[k*p] -= g[k]if sum(g) < K:lb = melse:ub = mfor d in range(1, N+1):if (d*lb+D-1)//D <= d*ub//D:n = d*ub//Dif flip:d, n = n, dprint(f"{n}/{d}")returnT = int(input())for _ in range(T):N, K = map(int, input().split())solve(N, K)