[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):

	import java.util.Scanner;
	import java.math.BigInteger;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while (T-- > 0) {
	int N = sc.nextInt();
	int B = sc.nextInt();
	BigInteger sum = BigInteger.ZERO;
	while (B-- > 0) {
	int K = sc.nextInt();
	BigInteger box = BigInteger.ONE;
	while (K-- > 0) {
	box = box.multiply(BigInteger.valueOf(sc.nextInt()));
	}
	sum = sum.add(box);
	}
	System.out.println(sum.remainder(BigInteger.valueOf(N)));
	}
	}
	}

view raw UVa10489.java hosted with ❤ by GitHub

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while (T-- > 0) {
	int N = sc.nextInt();
	int B = sc.nextInt();
	int ans = 0;
	while (B-- > 0) {
	int K = sc.nextInt();
	int tmp = 1;
	while (K-- > 0) {
	int ki = sc.nextInt();
	tmp *= ki;
	tmp %= N;
	}
	ans += tmp;
	ans %= N;
	}
	System.out.println(ans);
	}
	}
	}

view raw UVa10489_2.java hosted with ❤ by GitHub