問題來源：
HUST07校賽
原題見：
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1338
提交方式：
WOJ1338問題描述：
對于N（1<=N<=80)個數A[1...N](1<=A[i]<=500)，他們的和為sum，求sum!/(A[1]!*A[2]!*...*A[N]!)%40009。
解題過程：
對于這個題目，我當時就推出了上面的公式，然后就卡了，不知道后面怎么辦——這些數可是非常大。
其實這個問題的重點就在于運用擴展歐幾里德（感謝Felicia的指導）：
對于 a/b%m = ans, 求 ans。
a = a%m, b = b%m
ans = (a % m)*(x % m) % m （x為b的逆元）
求逆元則利用擴展歐幾里德：
對于 b*x = 1(mod m)
可以求b*x + m*y = 1的解（ 用extennd_Euclid(b, m, x, y) )!
然后把 x 映射到 [0,m)區間，帶入上式， 即得解。附代碼：
1
2 int extend_Euclid(int a, int b, int &x, int &y)
3 {
4 if (b == 0)
5 {
6 x = 1;
7 y = 0;
8 return a;
9 }
10 else
11 {
12 int ans = extend_Euclid(b, a % b, x, y); /////
13 int t = x;
14 x = y;
15 y = t - (a / b) * y;
16 return ans;
17 }
18 }
19
20
posted on 2008-03-14 16:46
R2 閱讀(2577)
評論(5) 編輯 收藏 引用 所屬分類:
Problem Solving 、
Pure Theory 、
Memo