题目 | 数字加减游戏 |
难度 | 难 |
题目说明 | 小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字 s 变成数字 t 。 每个回合,小明可以用当前的数字加上或减去一个数字。 现在有两种数字可以用来加减,分别为 a, b (a≠b),其中 b 没有使用次数限制。 请问小明最少可以用多少次 a,才能将数字 s 变成数字 t 。 题目保证数字 s 一定能变成数字 t。 |
输入描述 | 输入的唯一一行包含四个正整数s,t,a,b(1≤s,t,a,b≤),并且a≠b。 |
输出描述 | 输出的唯一一行包含一个整数,表示最少需要使用多少次 a 才能将数字 s 变成数字 t。 |
补充说明 | 无 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | 1 10 5 2 |
输出 | 1 |
说明 | 初始值 1 加一次 a 变成 6,然后加两次 b 变成 10,因此 a 的使用次数为 1。 |
示例2 | |
输入 | 11 33 4 10 |
输出 | 2 |
说明 | 11 减两次 a 变成 3,然后加三次 b 变成 33,因此 a 的使用次数为 2 次。 |
题目解读:
由于 a 加一次后再减一次等于 0,在这里需要计算最少次数,所以我们不必做既加又减的操作。同时,也假设 b 也只做一种操作,也不存在既加又减的情况。
在这个前提下,此题要求在 s 的基础上,加减若干次 a,再加减若干次 b,最后得到 t。
本质上,由 s 变成 t ,与 由 t 变成 s相比,加减 a 、b 的次数是一样的,无非就是逆向操作,加变减,减变加。
更进一步思考,s 变成 t,与 ( s + 1) 变成 ( t + 1 ) 也是一样的,其实就是发生 | s - t | 差值的变化。
分析与思路:
由于 s、t 是固定值,我们假设 n = | s - t |。
此题可以转变为:一个原始数据,加或减a 若干次(假设为 x),加或减 b 若干次(假设为 y),产生的变化为 n 。
此题有 3 种情况:
1. a * x - b * y = n
2. b * y - a * x = n
3. a * x + b * y = n
其中,x、y 均为正整数。
这 3 个等式可以做如下转换。
1. a * x - b * y = n y =
2. b * y - a * x = n y =
3. a * x + b * y = n y =
其中, 第 1 个 和 第 3 个 可以合并成 y = 。
在 y = 和 y = 这两个等式中,它们的分母都能被 b 整除,这意味着这两个等式可以转换成:
1. ( a * x ) % b = n % b
2. ( a * x ) % b = ( b - n % b) % b
这两个等式的右边都是常数。此题进一步简化:找出最小的 x,使其满足以上 2 个条件中的任意一个。
x 的取值范围是多少呢?由于等式对 b 进行取模操作,即意味着当 x == 0 等同于 x == b, x == 1 也等同于 x == ( b + 1)。直观地看, x 的取值范围为 0 ≤ x < b。
更进一步,假设 a、b 的最小公倍数是 L,那么 a 加 次与 b 加 次是相等的,因此 x 的取值范围可以进一步缩小到 0 ≤ x < 。
那么,此题就可以简化成,把 x 从 0 到 ,代入到等式
1. ( a * x ) % b = n % b
2. ( a * x ) % b = ( b - n % b) % b
中,当这两个等式中任意一个成立时,x 的值即是最小的值。
题目中提到,“题目保证数字 s 一定能变成数字 t”,那我们在从 x = 0 开始代入等式,每次增加 1 尝试等式是否成立时,无需去计算 的值,必定会在 之前求出 x 的值。
更进一步,先求 a 与 b 的最大公约数(设为 C1),再求 n 与 b 的最大公约数(C2),接着求 C1 和 C2 的最大公约数(设为 C),那么等式就变成了:
1. ( * x ) % = %
2. ( * x ) % = ( - % ) %
此时, 与 的最小公倍数变为原来的 ,x 的范围进一步缩小。
但是,写代码的时候完全不必关心这些。尽管 x 的取值范围进一步缩小,实际上是进一步精确了,x 的值不会发生改变,从 0 开始遍历,遍历的次数不会发生改变。
此题空间复杂度为 O(1)。由于输入数字最大不超过10的5次方,运行时间很短。
Java代码
- import java.util.Scanner;
-
- /**
- * 数字加减游戏
- *
- * @since 2023.09.08
- * @version 0.1
- * @author Frank
- *
- */
- public class NumPlusMinusGame {
-
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- while (sc.hasNext()) {
- String input = sc.nextLine();
- String[] numbers = input.split( " " );
- processNumPlusMinusGame( numbers );
- }
- }
-
- private static void processNumPlusMinusGame( String numbers[] )
- {
- int s = Integer.parseInt( numbers[0] );
- int t = Integer.parseInt( numbers[1] );
- int a = Integer.parseInt( numbers[2] );
- int b = Integer.parseInt( numbers[3] );
-
- int n = Math.abs( s - t );
-
- // 当modValue1 可能等于 modValue2,如 modValue1 等于0 或 等于 b/2 的情况。
- int modValue1 = n % b;
- int modValue2 = ( b - n % b ) % b;
-
- int i = 0;
- while( true )
- {
- int tmpModValue = ( a * i ) % b;
- if( tmpModValue == modValue1 || tmpModValue == modValue2 )
- {
- System.out.println(i);
- return;
- }
- i ++;
- }
- }
- }
JavaScript代码
- const rl = require("readline").createInterface({ input: process.stdin });
- var iter = rl[Symbol.asyncIterator]();
- const readline = async () => (await iter.next()).value;
- void async function() {
- while (line = await readline()) {
- var numberArr = line.split(" ");
- processNumPlusMinusGame(numberArr);
- }
-
- }();
-
- function processNumPlusMinusGame(numberArr) {
- var s = parseInt(numberArr[0]);
- var t = parseInt(numberArr[1]);
- var a = parseInt(numberArr[2]);
- var b = parseInt(numberArr[3]);
-
- var n = Math.abs(s - t);
-
- // 当modValue1 可能等于 modValue2,如 modValue1 等于0 或 等于 b/2 的情况。
- var modValue1 = n % b;
- var modValue2 = (b - n % b) % b;
-
- var i = 0;
- while (true) {
- var tmpModValue = (a * i) % b;
- if (tmpModValue == modValue1 || tmpModValue == modValue2) {
- console.log(i);
- return;
- }
- i++;
- }
-
- }
此题主要工作量在解题思路上,代码量非常少。
(完)