・(Xmodi)=X−i∗floor(X,i)
この関係式を使ってansの値を整理します。
ans
=∑i=1Y{X−i∗floor(X,i)}
=XY−∑i=1Y{i∗floor(X,i)}
です。
floor(X,i)の値は、floor(X) より大きいものと、それ以下のもののグループに分けることができます。
前者に関しては、それを与えるiの種類は高々floor(X)個ほどしかないため、O(X)で全探索することができます。
後者に関しては、ある固定された自然数kに対し、floor(X,i)=k となるようなiについて考えると、iは
floor(X,k+1)<i≤floot(X,k)
という連続した範囲で与えられることがわかります。
従って、それぞれのkに対して、floor(X,i)∗iの合計値をO(1)で得られるため、
後者もO(X)で求められます。
以上より、∑i=1Y{i∗floor(X,i)}の値はO(X)で計算できるので、ansもO(X)で求めることができます。
C/C++などの言語を用いる際はオーバーフローに注意してください。