如果一个数字是Good Number，当且仅当x开K次方后，能整除 x 。（注意是整除x,不是整除以x) 即x能整除以（x开K次方后的数）
现在给出 n,k ，求 1 到 n 之中Good Number 的个数。
第一个一个整数 T 表示测试组数。
之后每一行两个正整数 n,k。
1≤T≤10
1≤n,k≤10e9
"Case #x: y"格式输出，一行一个答案。
输入：
2 233 1 233 2输出：
Case #1: 233 Case #2: 43思路：特判一部分数据，暴力一部分数据，就不会超时啦！
(1) 当k==1时，1~n内所有数开一次方都是其本身，所以必然会被本身所除！即输出结果为n
(2) 当k>=30时 因为2^30=1073741824 大于题目所给的范围，所以在题目所给范围的任意一个数，开30次方后，向下取整，结果都为1，这时（题意中）任何数除以1都等于本身，都可满足条件，所以输出结果为n
(3) 2~30以内 以k=2为例：
【1,3】 开K次方后，向下取整为1，所以这区间里面三个数都可以
【4,8】开K次方后，向下取整为2，可以整除的数有4 6 8 三个
【9,15】开K次方后，向下取整为3，可以整除的数有 9 12 15 三个
【16,24】开K次方后，向下取整为4，有16 20 24
发现可行的个数=区间的两端的数值相减/此区间对应的向下取整的数;
即【1,3】–>(3-1)/1+1
【4,8】–>(8-4)/2+1。。。
其实k=3 4 5…都是一样的，不信你在纸上推算一下！
好了，是不是感觉说了个寂寞，还是没看懂？那。。。 看代码吧。。。
#include<bits/stdc++.h> using namespace std; long long a[4000000],b[4000000];//a记录次方数,b记录底数 //先来个快速幂模板 long long fastpow(long long a,long long b)//辅助找到a b里面的值 { long long re=1; while(b) { if(b&1) re*=a; a=a*a; b>>=1; } return re; } int main() { int t; scanf("%d",&t); for(int o=1;o<=t;o++) { long long n,k; scanf("%lld%lld",&n,&k); if(k==1||k>=31) //保险一点搞31吧 (怂怂的小声BB) { printf("Case #%d: %lld\n",o,n); continue; } long long j=1,len=0; for(int i=1;;i++) { long long x=fastpow(j,k); if(x>n) break;//如果范围超出的话，跳出循环 a[i]=x;//记录次方数 b[i]=j;//记录底数 j++; len++; } long long res=0;//记录结果 for(int i=2;i<=len;i++) { res+=(a[i]-1-a[i-1])/b[i-1]+1; //printf("%lld %lld %d\n",a[i]-1-a[i-1],b[i-1],res); } //如果n是一个次方数，直接加上1 if(b[len]==n) res+=1; else res+=(n-a[len])/b[len]+1; printf("Case #%d: %lld\n",o,res); } return 0; }运行正确`(∩_∩)′
然后。。。欢迎大家友好评论哈，要是哪里不对的，我再修改修改<(ToT)>，哪里语言表达不清的，我再学学语文？
