【简单数学】fzu2147A-B Game

(⊙v⊙)嗯……n多天没写题解了,主要是觉得水题有点多……不是水题的题解今天开始要慢慢补上……

A-B Game

Description
Fat brother and Maze are playing a kind of special (hentai) game by two integers A and B. First Fat brother write an integer A on a white paper and then Maze start to change this integer. Every time Maze can select an integer x between 1 and A-1 then change A into A-(A%x). The game ends when this integer is less than or equals to B. Here is the problem, at least how many times Maze needs to perform to end this special (hentai) game.
Input
The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow, each case contains two integers A and B described above.
1 <= T <=100, 2 <= B < A < 100861008610086
Output
For each case, output the case number first, and then output an integer describes the number of times Maze needs to perform. See the sample input and output for more details.
Sample Input
2
5 3
10086 110
Sample Output
Case 1: 1
Case 2: 7

大意:

输入两个数a,b。每次让 a=a-(a%x),   其中   1<=x<=a-1;问最少多少次操作才能使得a<=b。

思路:每次肯定要让s尽量变得更小,很容易想到当x=a/2+1时,(a/x)*x最小,所以每次变换a = a - ((a - 1) / 2)

注意a的范围,要用long long

#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
using namespace std;

long long  a, b;
long t;
void deal(long long a, long long  b)
{
    long sum = 0;
    while (a > b)
    {
        a -= ((a - 1) / 2);
        sum++;
    }
    printf("%d\n", sum);


}
int main()
{
    freopen("H.in","r",stdin);
    scanf("%d", &t);
    for (long i = 1; i <= t; i++)
    {
        scanf("%I64d%I64d\n", &a, &b);
        printf("Case %d: ", i);
        deal(a, b);

    }

    return 0;
}



全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
07-15 18:09
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务