C. Sad powers

Codeforces

IDCF955C

Time2000ms

Memory256MB

Difficulty—

binary searchmathnumber theory

English · Original

Chinese · Translation

Formal · Original

You're given _Q_ queries of the form (_L_, _R_). For each query you have to find the number of such _x_ that _L_ ≤ _x_ ≤ _R_ and there exist integer numbers _a_ > 0, _p_ > 1 such that _x_ = _a__p_. ## Input The first line contains the number of queries _Q_ (1 ≤ _Q_ ≤ 105). The next _Q_ lines contains two integers _L_, _R_ each (1 ≤ _L_ ≤ _R_ ≤ 1018). ## Output Output _Q_ lines — the answers to the queries. [samples] ## Note In query one the suitable numbers are 1 and 4.

[{"iden":"statement","content":"给定 #cf_span[Q] 个形如 #cf_span[(L, R)] 的查询。\n\n对于每个查询，你需要找出满足 #cf_span[L ≤ x ≤ R] 且存在整数 #cf_span[a > 0] 和 #cf_span[p > 1] 使得 #cf_span[x = ap] 的 #cf_span[x] 的个数。\n\n第一行包含查询数量 #cf_span[Q] #cf_span[(1 ≤ Q ≤ 105)]。\n\n接下来的 #cf_span[Q] 行每行包含两个整数 #cf_span[L], #cf_span[R] #cf_span[(1 ≤ L ≤ R ≤ 1018)]。\n\n请输出 #cf_span[Q] 行 —— 每个查询的答案。\n\n在第一个查询中，符合条件的数是 #cf_span[1] 和 #cf_span[4]。 \n\n"},{"iden":"input","content":"第一行包含查询数量 #cf_span[Q] #cf_span[(1 ≤ Q ≤ 105)]。接下来的 #cf_span[Q] 行每行包含两个整数 #cf_span[L], #cf_span[R] #cf_span[(1 ≤ L ≤ R ≤ 1018)]。"},{"iden":"output","content":"请输出 #cf_span[Q] 行 —— 每个查询的答案。"},{"iden":"note","content":"在第一个查询中，符合条件的数是 #cf_span[1] 和 #cf_span[4]。 "}]"

**Definitions** Let $ Q \in \mathbb{Z} $ be the number of queries. For each query $ i \in \{1, \dots, Q\} $, let $ (L_i, R_i) \in \mathbb{Z}^2 $ denote the interval bounds. Let $ \mathcal{P} = \{ x \in \mathbb{Z}^+ \mid \exists\, a \in \mathbb{Z}^+, p \in \mathbb{Z}, p \geq 2 \text{ such that } x = a^p \} $ be the set of perfect powers (excluding $ p = 1 $). **Constraints** 1. $ 1 \leq Q \leq 10^5 $ 2. For each query $ i $: $ 1 \leq L_i \leq R_i \leq 10^{18} $ **Objective** For each query $ i $, compute: $$ \left| \mathcal{P} \cap [L_i, R_i] \right| $$ i.e., the number of perfect powers in the interval $ [L_i, R_i] $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "C. Sad powers",
    "description": {
      "content": "You're given _Q_ queries of the form (_L_, _R_). For each query you have to find the number of such _x_ that _L_ ≤ _x_ ≤ _R_ and there exist integer numbers _a_ > 0, _p_ > 1 such that _x_ = _a__p_.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF955C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given _Q_ queries of the form (_L_, _R_).\n\nFor each query you have to find the number of such _x_ that _L_ ≤ _x_ ≤ _R_ and there exist integer numbers _a_ > 0, _p_ > 1 such that _x_ = _a__p_.\n\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给定 #cf_span[Q] 个形如 #cf_span[(L, R)] 的查询。\\n\\n对于每个查询，你需要找出满足 #cf_span[L ≤ x ≤ R] 且存在整数 #cf_span[a > 0] 和 #cf_span[p > 1] 使得 #cf_span[x = ap] 的 #cf_span[x] 的个数。\\n\\n第一行包含查询...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nFor each query $ i \\in \\{1, \\dots, Q\\} $, let $ (L_i, R_i) \\in \\mathbb{Z}^2 $ denote the interval bounds.\n\nLet $ \\mathcal{P} = \\{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments