java - C語言演算法題-韓信點兵 解法？

Question

完全不知道怎麼下手??

Answer 1

這個。 。 。不知道怎麼說才好。 。 。

設共有 n 個人，三人一排，五人一排，七人一排，看最後一排剩下 a, b, c 人
不就是

n % 3 = a
n % 5 = b
n % 7 = c

下面不就很簡單了麼？
方法 1： 暴力
n 從 10 到 100 都試試看。這個不用我說了

方法 2： 數學方法（解同餘式-初等數經）

例題：
n % 3 = 2
n % 5 = 4

可以轉化成什麼呢？

设 n / 3 = x 余 2, n / 5 = y 余 4
==> 3x + 2 = 5y + 4
==> 3x = 5y + 2
x,y 在 自然数的最小解是 x = 4, y = 2
==> n 最小是 12
3 和 5 的最小公倍数 = 15
所以 n % 15 == 12

三個的話，先算兩個，再算第三個。

Answer 2

雷雷