問題一覧 > 通常問題

No.3101 Range Eratosthenes Query

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 75
作問者 : shobonvip / テスター : noya2
お気に入りにしたユーザー ProblemId : 12099 / 自分の提出
問題文最終更新日: 2025-04-11 21:20:50
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.
  • Find the number of cards Shakin eats.
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。