650 : 二項係数の積の約数

B(n)=k=0n(nk)B(n) = \displaystyle \prod_{k=0}^n {n \choose k} とする。二項係数の積である。 例えば B(5)=(50)×(51)×(52)×(53)×(54)×(55)=1×5×10×10×5×1=2500B(5) = {5 \choose 0} \times {5 \choose 1} \times {5 \choose 2} \times {5 \choose 3} \times {5 \choose 4} \times {5 \choose 5} = 1 \times 5 \times 10 \times 10 \times 5 \times 1 = 2500 である。

D(n)=dB(n)dD(n) = \displaystyle \sum_{d|B(n)} d とする。B(n)B(n) の約数の和である。 例えば B(5)B(5) の約数は 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500, 625, 1250, 2500 なので、 D(5)=1+2+4+5+10+20+25+50+100+125+250+500+625+1250+2500=5467D(5) = 1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 + 100 + 125 + 250 + 500 + 625 + 1250 + 2500 = 5467となる。

S(n)=k=1nD(k)S(n) = \displaystyle \sum_{k=1}^n D(k) とする。 S(5)=5736S(5) = 5736, S(10)=141740594713218418S(10) = 141740594713218418, S(100)mod1000000007=332792866S(100) \bmod 1\,000\,000\,007 = 332792866 が与えられている。

S(20000)mod1000000007S(20\,000) \bmod 1\,000\,000\,007 を求めよ。

最終更新

役に立ちましたか?