作者LPH66 (-858993460)
看板puzzle
标题[中译] ProjectEuler 365 A huge binomial coefficient
时间Sun Jan 1 02:03:54 2012
365. A huge binomial coefficient
http://projecteuler.net/problem=365
C(10^18,10^9) 这个二项式系数是个超过九十亿位的大数字。
令 M(n,k,m) 表示 C(n,k) 除以 m 的余数。
求 ΣM(10^18,10^9,p*q*r) 的结果，其中 1000<p<q<r<5000 且 p,q,r 皆为质数。
--
这题的讨论串上提到的那个定理我竟然没听过...(暴汗)
(连这样也给我蒙了个第十真是不好意思 XD)
--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.83
1F：→ utomaya:又是第37名 虽然说是Easy题 对我来说一点都不Easy 01/01 06:17
2F：→ utomaya:BTW 那个定理我也没听过 01/01 06:17
3F：→ LPH66:基本上我用的方法和讨论串中 wrongrook 的做法是一样的 01/01 07:53
4F：→ LPH66:只是我写成的是递回形式就是了... 01/01 07:53
5F：推 utomaya:做法跟我一样, 我也是暴力乘开, 但因为p很小 01/01 10:44
6F：→ utomaya:所以会有一堆重覆的(kp+1)*(kp+2)*...*(kp+p-1) 01/01 10:45
7F：→ utomaya:重覆的部份先算好有几份, 然候再乘上头跟尾多出来的部份 01/01 10:46
8F：→ utomaya:这方法需要用到威尔森定理, (p-1)!=-1 mod p (p需为质数) 01/01 10:54