牧僮點牛 - 拼圖

※ 引述《stimim (qqaa)》之銘言：
: 突然想到，如果把題目改變一下，一樣有三個條件：
: 1. 每 6 隻一數的話剩1隻，每7、8隻一數的話剩1隻
: 每9、10隻一數的話，剩1隻，但11隻一數的話就可以整除。
: 2. 我牧的牛不照過4000隻
: 3. 而且答案的每個數字加起來剛好是10。
: -------------------------------
: 其中，每7、8隻一數的意思是：
: 在數的時候，是這樣數:
: 7 8 7 8 ...
: 第一組有七隻，第二組有八隻，帶三組有七隻，以此類推，最後還剩一隻
: 每九十隻一數也是一樣的方法。
: --------------------------------
: 請問有幾隻牛？
(以下的所有變數皆為整數)

所以總牛數是 6a+1, 15b+1 or 15b+8, 19c+1 or 19c+10, 11d

而 15b+8 => 30b'+8 or 30b'+23 除以 6 的餘數是 2 或 5 不合

於是只有 15b+1 的可能 和 6a+1 合併起來是 30e+1

再和 11d 合併起來是 330f+121

最後和 19c+1 or 19c+10 合併起來則是 6270g+3421 或 6270g+4741

因此唯一一個可能是 3421 隻

---
計算過程是利用了中國剩餘定理

例如最後的 330f+121 和 19c+1 合併是這樣的:

首先計算出對應的乘數

(330,19) 的場合是: 除以 330 的餘數乘上 2641 除以 19 的餘數乘上 3630

(理由是 2641≡1 (mod 330) 且 2641≡0 (mod 19)
3630≡0 (mod 330) 且 3630≡1 (mod 19)

這兩個數字可以經由 ax+by=1 的整數解導出)

於是 121*2641+1*3630 = 323191 除以 330x19=6270 的餘數為 3421

---
順帶一提, 下一個符合數字和是 10 的答案是 22231=6270x3+3421

而 6270g+4741 這個形式中數字和是 10 的最小答案則是 111331=6270x17+4741

--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308

--