一个余数问题的思考

朱雀 2022-06-17 12:14 107阅读 0赞

刚刚在贴吧上看到一个很简单的算法小问题，顺便看到了很多人不同的思路。我觉得很有意思，所以也来研究一下。

问题如下：

> 一筐鸡蛋：  
> 1个1个拿，正好拿完。  
> 2个2个拿，还剩1个。  
> 3个3个拿，正好拿完。  
> 4个4个拿，还剩1个。  
> 5个5个拿，还差1个。  
> 6个6个拿，还剩3个。  
> 7个7个拿，正好拿完。  
> 8个8个拿，还剩1个。  
> 9个9个拿，正好拿完。  
> 问：筐里最少有几个鸡蛋？

题目很简单，我们可以直接用暴力穷举法。这当然是最简单的办法， 下面是这种方法的Kotlin代码。运行之后，得到结果为1449。

fun answer1() {
        var n = 0
        while (true) {
            if (n % 2 == 1 && n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 7 == 0 && n % 8 == 1 && n % 9 == 0) {
                break
            }
            n++
        }
        println(n)
    }

当然暴力穷举虽然简单，但是效率并不是很高，对于这个问题来说，循环运行了1449次。我们可以分析题目特点，简化循环的运行次数。

首先来看看题目，很明显第一句是废话，因为任何正整数都可以被1整除。然后是第二句，这表明这个数是一个奇数。第三句和第九句明显重复，可以被9整除，那么必然也可以被3整除，所以只看第九句就可以了。还有第五句需要注意一下，因为这里是被5除还差1个，所以是还剩4个。我看贴吧里有些人审题不严，导致做了一个错误答案。

经过一番分析，上面的题目就变成了下面这样的。

奇数
    能被9整除
    除以4余1
    除以5余4
    除以6余3
    能被7整除
    除以8余1

注意到7和9互质，所以答案必然是63的倍数，而且还是个奇数，所以是奇数倍。所以我们的代码可以改进一下。代码中的`count`用于统计循环次数，这次结果和上次一样，但是循环次数仅为12次，每次要判断的条件也减少了很多。

fun answer2() {
        var n = 63
        var count = 0
        while (true) {
            count++
            if (n % 4 == 1 && n % 5 == 4 && n % 6 == 3 && n % 8 == 1) {
                break
            }
            n += 63 * 2
        }
        println("n=$n,count=$count")
    
    }

当然还可以进一步优化。由于这个数除以5余4，可以想到该数的个位数字不是4就是9，但是由于是奇数，那么个位数必然是9，而且这个数是63的倍数。而`除以4余1`和`除以8余1`这两个条件可以简化为`除以8余1`。所以最后代码就变成了这样，循环仅仅循环了3次。

fun answer3() {
        var n = 63 * 3
        var count = 0
        while (true) {
            count++
            if (n % 8 == 1) {
                break
            }
            n += 630
        }
        println("n=$n,count=$count")
    }

我还看到贴吧上有人说用同余定理算，但是我比较笨，没理解怎么用同余定理来计算。不过以前我倒是遇到过类似的题目，所以最后来介绍一下。

我遇到的题目类似下面这样：

> 一个数除以2余1，除以3余2，除以4余3，这个数最小是几？

这个问题倒是有一个简便方法，由于余数恰好和除数只差1，所以如果在被除数上加1，那么它就可以同时被2、3、4整除，所以这个数最小应该是2、3、4的最小公倍数再减1，所以应该是23 。

回到我们这道题目来说，由于余数每次都不一样，所以没办法这么做。不过我想了想，能不能通过加一个数，让余数都变得相同。由于我数学不好，也不懂数论这些专业知识，所以直接用代码模拟一下，发现确实可以得到一个数，让答案加上这个数以后，所有余数都相同。这个数是1071，这时候余数都是0 。Kotlin代码如下。

fun cal() {
        val numbers = hashMapOf(
                2 to 1,
                3 to 0,
                4 to 1,
                5 to 4,
                6 to 3,
                7 to 0,
                8 to 1,
                9 to 0)
        var n = 0
        while (true) {
            n++
            for (k in numbers.keys) {
                val old = numbers[k]
                numbers[k] = (old!! + 1) % k
            }
            val set = numbers.values.toSet()
            if (set.size == 1) {
                break
            }
        }
        println("这个数是:$n")
    }

有了这个数，我们就可以用上面的方法来计算结果了。答案加上1071之后，可以被2-9的所有数整除，所以2-9的最小公倍数再减去1071，就是我们要求的答案。而2-9的最小公倍数也就是5-9的最小公倍数，是2520，再减去前面的1071，正好就是最一开始我们得到的答案1449！

如果大家有更好的思路，也可以告诉我，让我们互相学习，共同进步！