解き方は複数ありますが，実装が最も楽な解法を紹介します．
まず，の少数部分からなる数列を考えます．
このままでは扱いづらいので，を扱いやすい形に変形すると，以下のように表せます．
は明らかに周期性を持ちます．よって，もと同じ周期を持ちます．周期は，がの倍数ときなので，です．したがって，は，まで求めれば十分です．
以上から，が以下の式で表されることがわかります．
したがって，最終的に求めるべき答えは
なので，上記式を求めるのにかかる計算量は，となり，これはこの問題の実行時間制限に対して十分高速です．
式では複雑に見えますが，コードは以下のようになり，短くてわかりやすいです．