yukicoder No.673 カブトムシ
No.673 カブトムシ - yukicoder
とりあえず年目の元旦のときのカブトムシの数を漸化式で表してみると,
が成り立ちます. これを解くと,
となります. これをあるについて, で割った余りを求めたい訳ですが, 上の漸化式(特に下の式)を計算してから余りを取るには, とても大きな数になり, 整数型におさまらないことが予想できます. なので上の演算を考えます.
フェルマーの小定理からを繰り返し自乗法で求め, (を利用) , 上の漸化式をMODを取りながら慎重に積を取ります. 上の漸化式は元旦のカブトムシの数なので, それを求めた後でCと積をとると答えです.
#278116 No.673 カブトムシ - yukicoder