首页 > 代码库 > CSU_1410: 整数转换

CSU_1410: 整数转换

2024-07-21 00:03:33   216人阅读

Description

我们可以通过对一个整数A进行加1操作或者乘2操作使其转换为另一个整数B。
给出两个整数X,Y，计算至少需要多少步才能将X转换为Y。.

Input

输入的第一行包含一个整数T (1≤ T ≤ 500)，表示一共有T组测试数据。
每组测试数据占一行，包含两个整数X,Y (1≤ X ≤ Y ≤ 1018)。

Output

对于每组测试数据，输出至少需要多少步才能将X转换为Y。

Sample Input

3
1 1
3 10
2 11

Sample Output

0
3
4

HINT

对样例2的解释：只需3步即可将3转换为10：3-> 4 -> 5 -> 10。

对样例3的解释：只需4步即可将2转换为11：2-> 4 -> 5 -> 10 -> 11。

Source

中南大学第八届大学生程序设计竞赛

//从y到x逆向考虑，注意用long long
#include<cstdio>
long long a,b;
void solve()
{
    long long ans=0;
    while(a<b)
    {
        if(a>b/2)
        {
            ans+=b-a,b=a;//a>b/2那么a变成b只能是一个个加1
        }
        else
        {
            if(b%2) ans+=2,b/=2;//b%2的余数不等于0那么a必须先加1，在乘以2
            else ans++,b/=2;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        solve();
    }
    return 0;
}


 

CSU_1410: 整数转换


联系
我们