[Java] UVa 10489 Boxes of Chocolates

題目連結

題意:
Little Pippy 有超多巧克力，她想平分給好朋友
要幫她計算最後分不完的數量

每組測資第一行先給 N, B
前者是好朋友人數，後者是巧克力盒數
接著 B 行各自給 K 與 a1, a2, ..., ak
表示每盒裡有 a1 小盒，每小盒裡又有 a2 小小盒...

最後求分給 N 個小朋友後剩多少無法平分

例如:
4 2
3 2 3 4
2 6 3

表示這組有 4 個朋友，2 盒巧克力
第 1 盒有 2 小盒，每小盒有 3 小小盒，每小小盒有 4 個巧克力
第 2 盒有 6 小盒，每小盒有 3 個巧克力
總共有 4*3*2 + 3*6 = 42 個巧克力
分給 4 個小朋友後，剩 2 個(除以 4 餘 2)

解法:
題目規定T, B, K 可以達到 100
ai上限可達10000，即最多可連乘 100 次 10000
所以全部相乘相加會爆掉

Java 用大數乘法可以AC

另外一解是用餘數的特性
(參考自演算法筆記)
我們把求 7 除以 5 的餘數記成以下:

7 mod 5 ≡ 2，其中 5 稱為模數

當模數相同時，餘數可以相加、相乘
如:
(7 mod 5) + (11 mod 5) ≡ (18 mod 5)
< (2+11) mod 5 ≡ 3 / 18 mod 5 ≡ 3 >(相加結果相同)

(2 mod 5) * (3 mod 5) * (4 mod 5) ≡ (24 mod 5)
< (2*3) mod 5 ≡ 1, (1*4) mod 5 ≡ 4 / 24 mod 5 ≡ 4 >(相乘結果相同)

以上相乘恰滿足題意提到的第一個盒子
因此，原本的作法是各自相乘後相加再 mod
可以變成各自 mod後再乘，mod 後再相加，最後再 mod 就是結果

參考資料:
演算法筆記 - Residue: http://www.csie.ntnu.edu.tw/~u91029/Residue.html

程式(Java):