305464: CF1036F. Relatively Prime Powers

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Relatively Prime Powers

题意翻译

对于一个数$x$,当且仅当将其分解后各个质因数的指数的最大公约数为$1$时,我们称这个数是合法的。 例子:$5(=5^1,\gcd(1)=1)$ $12(=2^2*3^1,\gcd(2,1)=1)$ $72(=2^3*3^2,\gcd(3,2)=1)$是合法的, 而 $8(=2^3,\gcd(3)=3)$ $100(=2^2*5^2,\gcd(2,2))$不是合法的。 有$T$组数据,对于每组数据,询问区间$[2,n]$中合法的数的个数。

题目描述

Consider some positive integer $ x $ . Its prime factorization will be of form $ x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots $ Let's call $ x $ elegant if the greatest common divisor of the sequence $ k_1, k_2, \dots $ is equal to $ 1 $ . For example, numbers $ 5 = 5^1 $ , $ 12 = 2^2 \cdot 3 $ , $ 72 = 2^3 \cdot 3^2 $ are elegant and numbers $ 8 = 2^3 $ ( $ GCD = 3 $ ), $ 2500 = 2^2 \cdot 5^4 $ ( $ GCD = 2 $ ) are not. Count the number of elegant integers from $ 2 $ to $ n $ . Each testcase contains several values of $ n $ , for each of them you are required to solve the problem separately.

输入输出格式

输入格式


The first line contains a single integer $ T $ ( $ 1 \le T \le 10^5 $ ) — the number of values of $ n $ in the testcase. Each of the next $ T $ lines contains a single integer $ n_i $ ( $ 2 \le n_i \le 10^{18} $ ).

输出格式


Print $ T $ lines — the $ i $ -th line should contain the number of elegant numbers from $ 2 $ to $ n_i $ .

输入输出样例

输入样例 #1

4
4
2
72
10

输出样例 #1

2
1
61
6

说明

Here is the list of non-elegant numbers up to $ 10 $ : - $ 4 = 2^2, GCD = 2 $ ; - $ 8 = 2^3, GCD = 3 $ ; - $ 9 = 3^2, GCD = 2 $ . The rest have $ GCD = 1 $ .

Input

题意翻译

对于一个数$x$,当且仅当将其分解后各个质因数的指数的最大公约数为$1$时,我们称这个数是合法的。 例子:$5(=5^1,\gcd(1)=1)$ $12(=2^2*3^1,\gcd(2,1)=1)$ $72(=2^3*3^2,\gcd(3,2)=1)$是合法的, 而 $8(=2^3,\gcd(3)=3)$ $100(=2^2*5^2,\gcd(2,2))$不是合法的。 有$T$组数据,对于每组数据,询问区间$[2,n]$中合法的数的个数。

加入题单

上一题 下一题 算法标签: