首页 > 代码库 > CSU 1410: 整数转换（数学啊 ）

CSU 1410: 整数转换（数学啊 ）

2024-08-06 16:44:26   210人阅读

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1410


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

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


PS:

逆向考虑；

代码如下：

#include <cstdio>
#include <cstring>
#define LL long long
int main()
{
    int t;
    LL a, b;
    LL k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&a,&b);
        k = 0;
        while(a < b)//逆向
        {
            if(2*a > b)//2*a>b那么a变成b只能是一个个加1  
            {
                k+=b-a;
                break;
            }
            else
            {
                if(b%2)//b%2的余数不等于0,那么a必须先加1，在乘以2 
                {
                    k+=2;
                }
                else
                {
                    k++;
                }
                b/=2;
            }
        }
        printf("%lld\n",k);
    }
    return 0;
}

再贴一发正向的：

#include <stdio.h>

int main()
{
	long long t,n,m,ci,er;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		ci=0;
		er=1;
		while(n*2<=m)
		{
			n*=2;
			ci++;
			er*=2;
		}
		while(er!=0)
		{
			if((m-n)%er==0)
			{
				ci+=(m-n)/er;
				break;
			}
			else 
			{
				ci+=(m-n)/er;
				n+=(m-n)/er*er;
				er/=2;
			}
		}
		printf("%lld\n",ci);

	} 
	return 0;
}


CSU 1410: 整数转换（数学啊 ）


联系
我们