題意：

如果一個(gè)數(shù)字是Good Number，當(dāng)且僅當(dāng) $?\sqrt[k]{x}?$(向下取整) 能整除 x 。

現(xiàn)在給出 n,k ，求 1 到 n 之中Good Number 的個(gè)數(shù)。

題目：

Alex loves numbers.

Alex thinks that a positive integer x is good if and only if $?\sqrt[k]{x}?$ divides x.

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

Input

The first line of the input gives the number of test cases, T (1≤T≤10). T test cases follow.

For each test case, the only line contains two integers n and k (1≤n,k≤$10^9$).

Output

For each test cases, output one line containing “Case #x: y”, where x is the test case number (starting from 1), and y is the answer.

Example

Input

2
233 1
233 2

Output

Case #1: 233
Case #2: 43

分析：

1.特判 首先對(duì)于 m=1，m>32 判斷一下，如果成立直接輸出 n ，因?yàn)?$2^{32}$>109 ，開(kāi)根號(hào)之后只能是 1 。
2.之后遍歷（1~n）的m次方數(shù)，接下來(lái)操作舉例演示：
例如 m=2 ，n=20 ，用 arr 記錄 x ，用 brr 記錄 xk 。

對(duì)于 1~3 之間的數(shù)字開(kāi)根號(hào)向下取整為1，故1~3之間的數(shù)字都是Good Number。4~8之間的數(shù)字開(kāi)根號(hào)都為2，有 8?4=4 個(gè)數(shù)字(分別是 5,6,7,8) ，其中有2個(gè)數(shù)字能被2整除，而 4 本身也能被 2 整除。所以對(duì)于4~8區(qū)間內(nèi)的Good Number個(gè)數(shù)為 (8?4)/2+1。同理 9~15 之間的數(shù)字開(kāi)根號(hào)都為 3 ，Good Number 個(gè)數(shù)為 (15?9)/3+1。對(duì)于最后的 16~20 ，開(kāi)根號(hào)都為4，所以最后加上 (n?16)/4+1 。

AC代碼：

#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; int t,k; ll n,m,ans; int main(){scanf("%d",&t);k=0;while(t--){scanf("%lld%lld",&n,&m);printf("Case #%d: ",++k);if(m==1)printf("%lld\n",n);else{ans=0;for(ll i=1;i<=n;i++){ll x=i,y=i+1;if(i==1){for(int j=1;j<m;j++){y=y*(i+1);if(y>n) break;}}else{for(int j=1;j<m;j++){x=x*i;y=y*(i+1);if(x>n) break;}}if(x>n) break;x=x-1;y=min(n,y-1);ll tep=y/i-x/i;ans+=y/i-x/i;}printf("%lld\n",ans);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Good Number Gym - 102769G 2020年CCPC秦皇岛分站赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。