{"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## Input\n\nThe first line contains the number of queries _Q_ (1 ≤ _Q_ ≤ 105).\n\nThe next _Q_ lines contains two integers _L_, _R_ each (1 ≤ _L_ ≤ _R_ ≤ 1018).\n\n## Output\n\nOutput _Q_ lines — the answers to the queries.\n\n[samples]\n\n## Note\n\nIn query one the suitable numbers are 1 and 4.","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第一行包含查询数量 #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]。 \"}]\"","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} = \\{ 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 $).\n\n**Constraints**  \n1. $ 1 \\leq Q \\leq 10^5 $  \n2. For each query $ i $: $ 1 \\leq L_i \\leq R_i \\leq 10^{18} $\n\n**Objective**  \nFor each query $ i $, compute:  \n$$  \n\\left| \\mathcal{P} \\cap [L_i, R_i] \\right|  \n$$  \ni.e., the number of perfect powers in the interval $ [L_i, R_i] $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF955C","tags":["binary search","math","number theory"],"sample_group":[["6\n1 4\n9 9\n5 7\n12 29\n137 591\n1 1000000","2\n1\n0\n3\n17\n1111"]],"created_at":"2026-03-03 11:00:39"}}