AtCoder Regular Contest 107 A - Simple Math( Python (3.8.2))

最近レートの上がりが調子良くて今日も暖まりたいと望んだARC107
結果は...

しかし、A問題に面白い数問が出たので紹介したいと思います。

- 問題を見て思ったこと
何だこれ！！「制約が10^9だからfor文は１度も使えない...」
絶対解くヒントがあるはずだと思い書いてみたら案外単純なものだった。

- 解法
実際にこの３重シグマを展開してみると、

$\displaystyle \sum_{a=1}^{A}\sum_{b=1}^{B}\sum_{c=1}^{C} abc \\ = \{(1\times1\times1) + (1\times1\times2) + ... + (1\times1\times c)\} + (1\times2\times1) + ... \\ = 1\times1\times(1+2+ ... + c) + 1\times2\times(1 + 2 + ... + c) + ... \\ = 1\times(1 + 2 + ... + b)\times(1 + 2 + ... + c) + 2\times(1 + 2 + ... + b)\times(1 + 2 + ... + c) + ...\\ =(1 + 2 + ... + a)\times(1 + 2 + ... + b)\times(1 + 2 + ... + c)\\ =\frac{a(a+1)}{2}\frac{b(b+1)}{2}\frac{c(c+1)}{2}$

したがって、

$\displaystyle \sum_{a=1}^{A}\sum_{b=1}^{B}\sum_{c=1}^{C} abc \\ =\frac{1}{8}a(a+1)b(b+1)c(c+1)$

という式が得られます。

したがって以下のようなコードでACすることが可能です。
- 参考コード

a,b,c = map(int,input().split())
mod = 998244353
print((a*(a+1)//2 * b*(b+1)//2 * c*(c+1)//2)%mod)

- 最後に
数学問題をこれからも低頻度で上げていくつもりです。
精進頑張る！！！