4942. 砝码称重 - AcWing题库

1、题目

给定一个天平和 101 个砝码。

101 个砝码的重量依次为 n⁰,n¹,n²,…,n¹⁰⁰ 克，其中 n 是一个不小于 2 的整数。

请你判断，我们能否利用给定天平和砝码对重量为 m 克的物品进行称重。

注意，天平的两端都可以放入砝码。

具体来说，你的任务是判断是否可以在天平的左盘放入重量为 m克的物品以及一些砝码（也可以不放砝码），并在天平的右盘放入一些砝码，从而使得天平的两端可以保持平衡。

不要求用到所有砝码，挑选合适的砝码使用即可。

例如，如果 n=3,m=7，则我们可以在天平的左盘放入重量为 7 克的物品以及重量为 3 克的砝码，并在天平的右盘放入重量为 1,9克的砝码，这样可以使得天平两端保持平衡。

输入格式

共一行，包含两个整数 n,m。

输出格式

如果可以对重量为 m 克的物品进行称重，则输出 YES，否则输出 NO。

数据范围

前 5 个测试点满足 2≤n≤100，1≤m≤100。

所有测试点满足 2≤n≤10⁹，1≤m≤10⁹。

输入样例1：

3 7

输出样例1：

YES

输入样例2：

100 99

输出样例2：

YES

题目解读

题目会给两个数，n和m，要求我们可以使用 101 个砝码（101 个砝码的重量依次 为 n⁰,n¹,n²,…,n¹⁰⁰ 克，其中 n 是一个不小于 2 的整数）。是否可以在天平的左盘放入重量为 m克的物品以及一些砝码（也可以不放砝码），并在天平的右盘放入一些砝码，从而使得天平的两端可以保持平衡。

这可以转化成m是否可以由n进制表示出来，但是n进制上面的数只能是0（不放），1（放在物品对面），-1（放在物品这边），所以我们只需要求n进制的m每一位上面是否是0，1，-1，如果不是则说明无法对重量为 m克的物品进行称重，输出NO。

此时有小伙伴就发现了

m, n都是正数啊，两个取余不可能得到-1这个结果，那我们应该怎么办？

我们把判断 -1 换成判断 n-1

为什么可以这样换？Java中余数可以是负数，在数学中余数不能是负数

举个例子：-9%10 = -9（Java表示），-9%10 = -1* 10 + 1（数学表示）；

发现什么没，左边的 -9 和右边的 10 - 9 = 1 是一样的；

所以我们可以把判断-1换成判断n-1

10 9

9= -1 * 10⁰ + 1*10¹

3、代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        while (m!=0){
            int i=m%n;
            if (i!=0&&i!=1&&i!=n-1){
                System.out.println("NO");
                return;
            }
            if (i > 1)//i=n-1 转换回 n=-1
                i = -1;
            m = (m - i) / n;
        }
        System.out.println("YES");
    }
}