5只猴子是好朋友，在海边的椰子树上睡着了。这期间，有商船把大堆香蕉忘记在沙滩上。 第1只猴子醒来，把香蕉均分成5堆，还剩下1个，就吃掉并把自己的一份藏起来继续睡觉。 第2只猴子醒来，把香蕉均分成5堆，还剩下2个，就吃掉并把自己的一份藏起来继续睡觉。 第3只猴子醒来，把香蕉均分成5堆，还剩下3个，就吃掉并把自己的一份藏起来继续睡觉。 第4只猴子醒来，把香蕉均分成5堆，还剩下4个，就吃掉并把自己的一份藏起来继续睡觉。 第5猴子醒来，重新把香蕉均分成5堆，哈哈，正好不剩! 请计算一开始最少有多少个香蕉。
现把题目用同余方程来描述：
设开始最少有 个香蕉
则有：
化简最后一个方程，合并各项：
于是原式可表示为：
保证左式为整数，需满足：
所以：
方程可以重写为：
由于 和 的最大公约数 ，那么 在模 意义下有乘法逆元。
计算 在模 意义下的乘法逆元 ，使得 。
解得：
将方程两边同时乘以 ，得到 的解：
解得：
我们需要最小的有意义的正整数解
，结果为 16 时，第5猴子醒来没有香蕉了，无意义。
为最小有意义答案
证毕
附C++计算代码
#include <bits/stdc++.h>
using namespace std;
// 扩展欧几里得算法
int extgcd(int a, int b, int &x, int &y) {
int d;
if (b == 0)
x = 1, y = 0, d = a;
else {
d = extgcd(b, a % b, y, x);
y -= a / b * x;
}
return d;
}
// 扩展欧几里得算法求乘法逆元
int inv(int a, int b) {
int x, y;
if (extgcd(a, b, x, y) == 1)
return x;
return -1;
}
int main() {
// 256x - 4096 \equiv 0 \pmod{3125}
// 256a \equiv 1 \pmod{3125}
int a = inv(256, 3125);
cout << "a = " << a << '\n';
// x \equiv 4096a \pmod{3125}
int x = 4096 * a % 3125;
cout << "x = \n";
cout << x << '\n';
cout << x + 3125 << '\n';
cout << x + 3125 * 2 << '\n';
/* output
a = -354
x =
-3109
16
3141
*/
}