链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
给定两个整数 a,b (a≤b)a,b\ (a \leq b)a,b (a≤b),在一次操作中,你可以选择以下三个操作中的任意一个进行操作:
a+1
a*a
a*2
请求出将 aaa 变成 bbb 的最少操作次数。
输入描述:
第一行包含一个整数 T (1≤T≤50)T \ (1 \leq T\leq 50)T (1≤T≤50),表示测试用例的组数。
每组测试用例的第一行包含两个整数 a,b (1≤a≤b≤1012)a,b \ (1\leq a\leq b\leq10^{12})a,b (1≤a≤b≤1012)。
输出描述:
对于每组测试用例,输出一个整数,表示最少操作次数。
分析:
1.a的平方如果小于等于b,那么sqrt(b)>=a,那么可以反推,f(n)=f(sqrt(n))+1+n-sqrt(n)*sqrt(n)
2.a*2同理
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a,b;
ll dfs(ll md)
{
ll sums=0;
sums=md-a;
if(sums==0)return 0;
ll sq=sqrt(md);
if(sq>=a)sums=min(sums,dfs(sq)+1+md-sq*sq);
if(md/2>=a)sums=min(sums,dfs(md/2)+1+(md&1));
return sums;
}
void solve()
{
cin>>a>>b;
ll md=dfs(b);
cout<<md<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}