[中譯] ProjectEuler 365 A huge binomial coefficient

[LPH66 (-858993460)]

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
→ utomaya:又是第37名 雖然說是Easy題 對我來說一點都不Easy
→ utomaya:BTW 那個定理我也沒聽過
→ LPH66:基本上我用的方法和討論串中 wrongrook 的做法是一樣的
→ LPH66:只是我寫成的是遞迴形式就是了...
推 utomaya:做法跟我一樣, 我也是暴力乘開, 但因為p很小
→ utomaya:所以會有一堆重覆的(kp+1)*(kp+2)*...*(kp+p-1)
→ utomaya:重覆的部份先算好有幾份, 然候再乘上頭跟尾多出來的部份
→ utomaya:這方法需要用到威爾森定理, (p-1)!=-1 mod p (p需為質數)