指数部分はmodしてはいけない --No.673 カブトムシ--

Quiz

https://yukicoder.me/problems/no/673

AC Code

https://yukicoder.me/submissions/354019

解法

• 1日目はBC
• 2日目はBC(1+C)
• ...
• D日目はBC(1+...+C^D-1)
• よって等比数列の和の公式から解ける

前提知識

• フェルマーの小定理と繰り返し二乗法
  • https://www.hamayanhamayan.com/entry/2018/06/06/210256

落とし穴

• B, C, Dが大きいので最初にmodを取ったが、これは失敗だった
• 指数部分はmodを取ってはいけない

B %= mod;
C %= mod;
D %= mod;

• WAコード
  • https://yukicoder.me/submissions/354014

追記：2020/04/07

• 行列累乗で解きました
• https://yukicoder.me/submissions/460117