解き方は複数ありますが,実装が最も楽な解法を紹介します.
まず,AB×kの少数部分からなる数列Xkを考えます.
Xk=AB×k−floor(AB×k)
このままでは扱いづらいので,Xkを扱いやすい形に変形すると,以下のように表せます.
Yk=(B×k)modA
Xk=AYk
Ykは明らかに周期性を持ちます.よって,XkもYkと同じ周期を持ちます.周期は,B×kがlcm(A,B)の倍数ときなので,gcd(A,B)Aです.したがって,Xkは,Xgcd(A,B)Aまで求めれば十分です.
以上から,∑k=1NXkが以下の式で表されることがわかります.
∑k=1NXk=(floor(gcd(A,B)AN)×∑k=1gcd(A,B)AXk)+∑k=1Nmodgcd(A,B)AXk
=A(floor(gcd(A,B)AN)×∑k=1gcd(A,B)AYk)+∑k=1Nmodgcd(A,B)AYk
したがって,最終的に求めるべき答え∑k=1Nfloor(AB×k)は
∑k=1Nfloor(AB×k)
=∑k=1N(AB×k−Xk)
=∑k=1NAB×k−∑k=1NXk
=AB×∑k=1Nk−((floor(gcd(A,B)AN)×∑k=1gcd(A,B)AYk)+∑k=1Nmodgcd(A,B)AYk)
∑k=1Nk=2N×(N+1)なので,上記式を求めるのにかかる計算量は,O(gcd(A,B)A)となり,これはこの問題の実行時間制限に対して十分高速です.
式では複雑に見えますが,コードは以下のようになり,短くてわかりやすいです.