本文共 914 字，大约阅读时间需要 3 分钟。

正题

题目大意

给出$n$，求$[1..n]$中有多少个数可以被$a^b(b>1)$表示

解题思路

首先如果$b$等于$2$，那么可以被表示的数就是$\sqrt{n}$个

$b$不是质数时，显然所以的数都可以被一个$b$是质数的情况表示。

当$b$大于等于三时，$a$的个数级别不超过$10^6$，所以我们枚举后面的数。

需要考虑重复如$4^3=8^2$，其实这个重复本质上就是$(2^2{)}^3=(2^3{)}^2$，也就是说如果$a$可以表示为$k^q(q<b)$时，那么$a^b$一定已经被计算过了

$code$

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：http://bdwaf.baihongyu.com/