ABC-110:D

問題

atcoder.jp

提出

30分やってできなかったので諦めた。

紙

紙

思考

1. 素因数分解はする気がする。
2. 指数使ってどうするのか分からん。
3. 動的計画法考えても分からん。
4. ？？？

問題点

• 前も引っかかったことがあるが、そもそもM<10^9のMを素因数分解するときの計算量がsqrt(M)なのを忘れるし、その実装も忘れる気がする。
• 組み合わせ%MODをフェルマーの小定理を使って求めるやつを去年やろうとした（＝やってない）

実装

PDF見ても全く分からんので放送の奴を写経。

atcoder.jp

他人の提出

• 早い人はほぼ全員事前計算でint[] fact,factInvみたいなのを持ってて組み合わせを階乗の掛け算割り算にして計算している。
• ただこの場合事前計算する配列サイズが問題で今回のだと問題設定から10^5以上必要だが、10^6で計算すると1s強かかってしまう(java)。ので使い分けが必要？

フェルマーの小定理のまとめ

フェルマーの小定理のやつ

texで書こうとしたけどどうせ自分が見返す用なので写真でいいやって