CFR 616 E. Sum of Remainders ( Math, Sqrt Decomposition )

Problem - E - Codeforces

題意：
給 N, M，求：

資料規模：
The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.

解法：
首先觀察到

因此所求可以寫成

考慮比較簡單的這個問題：

這個的求法是基於平方分割，細節和這篇幾乎一樣。
那有了 M 這東西其實只要多判退出迴圈的時機。

時間 / 空間複雜度：
O( min( N, M )^0.5 )

import math
MOD = int( 1e9 + 7 )

N, M = map( int, input().split() )
sn = int( math.sqrt( N ) )

ans = N * M % MOD
for i in range( 1, min( sn, M ) + 1, 1 ):
  ans -= N // i * i
ans %= MOD

if N // ( sn + 1 ) > M:
  exit( print( ans ) )

for f in range( N // ( sn + 1 ), 0, -1 ):
  s = lambda x: x * ( x + 1 ) // 2
  if N // f > M:
    ans -= f * ( s( M ) - s( N // ( f + 1 ) ) )
    break
  ans -= f * ( s( N // f ) - s( N // ( f + 1 ) ) )
ans %= MOD

if ans < 0:
  ans += MOD
print( ans )