結果
問題 |
No.1567 Integer Coefficient Equation
|
ユーザー |
|
提出日時 | 2025-03-29 20:32:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,003 ms / 2,000 ms |
コード長 | 2,071 bytes |
コンパイル時間 | 573 ms |
コンパイル使用メモリ | 82,832 KB |
実行使用メモリ | 178,968 KB |
最終ジャッジ日時 | 2025-03-29 20:33:08 |
合計ジャッジ時間 | 41,322 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
## https://yukicoder.me/problems/no/1567 def main(): T = int(input()) parameters = [] for _ in range(T): p, l, r = map(int, input().split()) parameters.append((p, l, r)) # osa-k法による素因数分解 MAX_SIZE = 5 * 10 ** 5 primes = [i for i in range(MAX_SIZE + 1)] for p in range(2, MAX_SIZE + 1): if primes[p] != p: continue x = 2 * p while x <= MAX_SIZE: if primes[x] == x: primes[x] = p x += p dnum = [0] * (MAX_SIZE + 1) for a in range(1, MAX_SIZE + 1): a0 = a p_map = {} while primes[a] != 1: p = primes[a] a //= p if p not in p_map: p_map[p] = 0 p_map[p] += 1 p_array = [(p, v) for p, v in p_map.items()] p_array.sort(key=lambda x: x[1], reverse=True) dnum[a0] = p_array cum_dnum_lisst = [0] * (MAX_SIZE + 1) cum_dnum = 0 for i in range(1, MAX_SIZE + 1): p_array = dnum[i] if len(p_array) >= 3: cum_dnum += 1 elif len(p_array) == 2 and p_array[0][1] >= 2: cum_dnum += 1 elif len(p_array) == 1 and p_array[0][1] >= 4: cum_dnum += 1 cum_dnum_lisst[i] = cum_dnum # それぞれ回答していく answers = [] for p, l, r in parameters: if p < l: xr = r - p xl = l - p ans = cum_dnum_lisst[xr] - cum_dnum_lisst[xl - 1] elif p == l: xr = r - p ans = cum_dnum_lisst[xr] + 1 elif l < p and p < r: xr = r - p ml = p - l ans = cum_dnum_lisst[xr] + cum_dnum_lisst[ml] + 1 elif p == r: ml = p - l ans = cum_dnum_lisst[ml] + 1 else: # r < p: mr = p - r ml = p - l ans = cum_dnum_lisst[ml] - cum_dnum_lisst[mr - 1] print(ans) if __name__ == "__main__": main()