作者：R2@whuacm 来源：博客园 酷勤网收集 2008-03-15
摘要
对于这个题目，我当时就推出了上面的公式，然后就卡了，不知道后面怎么办——这些数可是非常大。其实这个问题的重点就在于运用扩展欧几里德。
问题来源：
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)区间，带入上式， 即得解。
附代码：
来自：http://www.cppblog.com/littlekid/archive/2008/03/14/extend_euclid.html
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_Gcd ( 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
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_Gcd ( 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
来自：http://www.cppblog.com/littlekid/archive/2008/03/14/extend_euclid.html