AcWing——砝码称重

4942. 砝码称重 - AcWing题库

给定一个和平的天平 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 = -(Java表示)-9%10 = -1* 10 + 1(数学表示)；

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

因此，我们可以将判断-1替换为判断n-1

10 9

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

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){            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");    }}