May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0

问题来源:
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 阅读(2291) 评论(5)  编辑 收藏 引用 所属分类: Problem SolvingPure TheoryMemo

FeedBack:
# re: 【数论】扩展欧几里德的一个妙用
2008-03-17 21:23 | 长江三峡
学习  回复  更多评论
  
# re: 【数论】扩展欧几里德的一个妙用
2008-03-17 21:42 | sdf
感觉ACM玩的东西都好复杂啊!!  回复  更多评论
  
# re: 【数论】扩展欧几里德的一个妙用
2008-04-07 21:48 | IceDragon
楼主你好,我也是用扩展欧几里得做的,但是我一直WA
可否借你的代码看下--不胜感激
这题目还有什么陷阱么??????
我邮箱--wangzhaoren@gmail.com
  回复  更多评论
  
# re: 【数论】扩展欧几里德的一个妙用
2008-04-09 12:53 | littlekid
@IceDragon
估计OJ出现不明错误,或者后来加强数据了(最近交的都没过,我贴了别人AC的代码都没过=,=!)

不过你可以考虑一下越界问题——用long long试试  回复  更多评论
  
# re: 【数论】扩展欧几里德的一个妙用
2009-10-29 17:59 | 5
还是不懂啊  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2019年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 53582
  • 排名 - 349

最新评论

阅读排行榜

评论排行榜