No.3101 Range Eratosthenes Query
問題文最終更新日: 2025-04-11 21:20:50
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 464
(順位表)
の他の問題:
Note
The time limit for this problem is 3.000 seconds.
Problem Statement
You are given $Q$ queries. In the $i$-th query, positive integers $L_i, R_i$ are given, so find the answer to the following [Problem].
[Problem]
- Initially, there is $1$ card each with $L_i, L_i+1, \cdots, R_i$ written on it, placed on a desk. Then, while there is at least $1$ card on the desk, Shakin repeats the following operation.
- Choose the card with the smallest value among the cards on the desk, and let that value be $k$. Shakin eats that card.
- Then, remove from the desk all cards on the desk whose written value is a multiple of $k$. The removed cards are not eaten.
Constraints
- All input values are integers.
- $1 \le Q \le 2 \times 10^5$
- $1 \le L_i \le R_i \le 10^6$ $(1\le i\le Q)$
Input
$Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
Output
Output $Q$ lines. On the $i$-th line $(1\le i\le Q)$, output the answer to the $i$-th query.
Sample
Sample 1
Input
5 1 20 2 20 3 20 4 20 5 20
Output
1 8 8 9 9
- In the $1$st query, Shakin eats the cards with the following values: $1$
- In the $2$nd query, Shakin eats the cards with the following values: $2, 3, 5, 7, 11, 13, 17, 19$
- In the $3$rd query, Shakin eats the cards with the following values: $3, 4, 5, 7, 11, 13, 17, 19$
- In the $4$th query, Shakin eats the cards with the following values: $4, 5, 6, 7, 9, 11, 13, 17, 19$
- In the $5$th query, Shakin eats the cards with the following values: $5, 6, 7, 8, 9, 11, 13, 17, 19$
Sample 2
Input
5 12 345678 2025 870777 100000 1000000 1000000 1000000 1 1
Output
29639 100000 338570 1 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2