Alex loves numbers.

Alex thinks that a positive integer x is good if and only if [⌋ divides x.

Can you tell him the number of good positive integers which do not exceed n ?

题意：

当一个x满足[⌋能乘除x时，x就是一个好数
问1~n内有多少好数

题解：

推一推规律：
我们用将数分成一块一块
以k=2为例：
[1,3] 向下取整为1，左端点减右端点为2，答案是3
[4,8] 向下取整为2，左端点减右端点为4，答案是3
[9,15] 向下取整为3，左端点减右端点为6，答案是3
....
[36,48] 向下取整为6，左端点减右端点为12，答案是3

其实区间的答案=左端点减右端点/向下取整 +1
这是k等于2的情况，k等于其他可以枚举试试
其实本质就是一个找规律的题
注意：
当k过大时，当k>=30是，我们n即便取最大值，开k次方后还是1，所以此时答案就是n
当k=1时答案也是1
除了试出答案其实是严格的推导过程，我就简单提一下
但提一提
一个十分经典的数学问题[1,n]以内有多少数能被x整除——答案就是⌊⌋
然后利用容斥去推导
区间[a,b]有多少个能被x整除的数：
⌊⌋ - ⌊⌋
剩下的我也不清楚了。。。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+9;
int sum[maxn];
int b[maxn];
typedef long long ll;
ll poww(int a,int b)
{
    ll sum=1;
    while(b)
    {
        if(b&1)sum*=a;
        a=a*a;
        b>>=1;
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int ii=1;ii<=t;ii++){

        memset(sum,0,sizeof(sum));
        memset(b,0,sizeof(b));
        int n,k;
        cin>>n>>k;
        if(k==1||k>=31)
        {
          printf("Case #%d: %lld\n",ii,n);
          continue;    
        }
        int len=0;
        int pos=0;
        ll ans=0;
        for(int i=1;i;i++)
        {
            ll x=poww(i,k);//x 
            if(x>n)
            {
                sum[len]=(n-pos);
                b[len]=i-1;
                break;
            }
            if(i!=1)
            {
                sum[len]=(x-1)-pos;
                b[len]=i-1;
            }
            if(i==n)ans++;
            len++;
            pos=x;
        }

        for(int i=1;i<=len;i++)
        {
            ans+=(sum[i]/b[i])+1;
        }
        printf("Case #%d: %d\n",ii,ans);
    }
} 
/*
1
3133 29
*/