【简单数学】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;
}
投递歌尔股份等公司9个岗位 >
查看3道真题和解析