克拉克是一名人格分裂患者.某一天克拉克变成了一名数论研究者,在研究数字.
他想到了一个题:给定非负整数 x 和正整数 k ,可以做若干操作,每次操作是以下两种方法之一:
1. x=x−k
2. x=⌊x√⌋2
现在克拉克想知道,这个整数最少经过多少次操作可以变成 0 .
Input
第一行是一个正整数T(1≤T≤100),表示数据组数. 每组数据只有一行两个整数x, k(0≤x≤10^18, 1≤k≤2).Output
每组数据输出一行一个整数,表示最少的操作数.若不存在方案,输出-1Input示例
2 2 1 3 2Output示例
2 -1
可以进行两种操作 1. x-k 2 x=⌊x√⌋2
k要么是1要么是2，首先看操作，可以使一个数减k。或者是x下到一个平方梯度。
比如，4 9 16 25 36，分别是2,3,4,5,6的平方，如果x刚好大于哪个，操作2可以直接跳到那个平方数
从一个平方数跳到下一个平方数最快需要两步，先1后2，就算是9到跳4，如果单纯一直减k至少3步（算k为2）
一开始若x等于平方数就不用说了，如果大于就操作2直接跳到平方数，需要一步，再跳下一个平方数两步
比如：x=35 ,先2操作，x=25，再1，x=24,再2，x=16,一共三步，也是最少步数的方法（除了特例）
但是也有特殊情况，当k=2时，一开始的归平方数和减1可以一步完成，再归平，只需要两步
比如：x=26，先2，x=25,再1,x=23,再2,x=16. 一共三步
但是先2再1其实就减了2，原本1操作是为了x不等于平方数，配合2操作能跳到下一个平方数
x=26,先1, x=24,再2，x=16 一共两步
数据大小10的18次方，无论k为多少，当x减到4都能变成0，先用答案计算数值到一个平方数的步数
然后开方减去2乘2: (sqrt(x)-2)*2,从一个平方数到下一个需要两步，计算与4差多少个平方数直接开方后减就好了
计算答案有个bug的地方，就是精度问题，导致sqrt(999999999.......)=10000000000....
可以用二分找到刚好小于他的平方数解决，也可以对它开方后平方，与原数据处理，sqrt(x)^2>x，就对ans处理
当x<=4使，一开始判断分析，直接输出答案跳过。
if(n==0) cout<<"0"<<endl; if(n==1&&k==1) cout<<"1"<<endl; if(n==2) cout<<n/k<<endl; if(n==3&&k==1) cout<<"2"<<endl; if((n==3&&k==2)||(n==1&&k==2)) cout<<"-1"<<endl;
附上代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<string.h> #include<math.h> using namespace std; int main() { long long int sqr,cha,ok=0,ans=0;//sqr是开方后的数值，cha是开方后再平方与原来的差值，ok是标志在这无作用 long long int cas,n,k; //ans是步数 cin>>cas; while(cas--) { ans=0; cin>>n>>k; if(n==0) { cout<<"0"<<endl; continue; } if(n==1&&k==1) { cout<<"1"<<endl; continue; } if(n==2) { cout<<n/k<<endl; continue; } if(n==3&&k==1) { cout<<"2"<<endl; continue; } if((n==3&&k==2)||(n==1&&k==2)) { cout<<"-1"<<endl; continue; } sqr=sqrt(double(n)); // cout<<"sqr="<<sqr<<endl; cha=n-sqr*sqr; //cout<<"cha="<<cha<<endl; if(cha==0) ok=1; else if(cha==1&&k==2&&n>9) { ans+=2; sqr--; } else if(cha<0) { ans++; sqr--; } else { ans++; } ans+=(sqr-2)*2; ans+=2; if(k==1) ans++; cout<<ans<<endl; } return 0; }
