包除原理を用いると、答えは

\(N\) 以下で\(A\) の倍数でも \(B\) の倍数でもないものの総和 \(=\) \(N\) 以下の総和 \(-\) \(N\) 以下の\(A\) の倍数の総和 \(-\) \(N\) 以下の\(B\) の倍数の総和 \(+\) \(N\) 以下の\(A\) の倍数かつ \(B\) の倍数であるものの総和

と変形できます。さらに、 \(A\) の倍数かつ \(B\) の倍数であるものは、 \(A\) と \(B\) の最小公倍数の倍数と言い換えられます。

ここで、\(N\) 以下の\(A\) の倍数の総和は、\(A(1+2+\ldots+\lfloor N / A \rfloor)\) と書けるので、\(f(n) := 1 + 2 + \ldots + n = n(n+1)/2\)、\(L := \mathrm{LCM}(A,B)\) とおけば、答えは \(f(N) - Af(\lfloor N / A \rfloor) - Bf(\lfloor N / B \rfloor) + Lf(\lfloor N / L \rfloor)\) となります。

以上より、最小公倍数を求めるのがボトルネックとなり、この問題は \(\mathrm{Ο}(\log \mathrm{min}(A,B))\) で解けます。