PE 401 Sum of squares of divisors ( Math, Sqrt Decomposition )

Well, I know that posting this might no be completely appropriate but...

題意：
問 [ 1, 1e15 ] 所有整數的因數平方總和為多少。

解法：


也就是平方分割，而枚舉 d 轉換成枚舉 N // d 那部分我一直很搞不清楚，但其實只要知道這件事就可以理解：

這件事成立，因為


又有以下恆式：

因為


套回到原本那兩個式子的下方那條：

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

import math

MOD = int( 1e9 )
N = int( 1e15 )

sn = int( math.sqrt( N ) )

ans = 0

for d in range( 1, sn + 1, 1 ):
  ans += N // d * d * d
  ans %= MOD

def s2( x ):
  return x * ( x + 1 ) * ( 2 * x + 1 ) // 6

for f in range( N // ( sn + 1 ), 0, -1 ):
  ans += f * ( s2( N // f ) - s2( N // ( f + 1 ) ) )
  ans %= MOD

print( ans )