HE Numbers Summation ( OEIS, Math, Square Root Decomposition )

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/

題意：
給 N，求 S 對 1e9 + 7 取模。

制約：
1 ≤ N ≤ 1e15

解法：
無恥怒查 OEIS。
如果想認真解起來，要領應該跟這個是一樣的。

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

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = int( 1e9 ) + 7;
 
long long N;
 
int int_pow( int v, int p, int m ) {
  int res = 1;
  while( p ) {
    if( p & 1 ) {
      res = 1LL * res * v % m;
    }
    p >>= 1;
    v = 1LL * v * v % m;
  }
  return res;
}
 
int inv( int v ) {
  return int_pow( v, MOD - 2, MOD );
}
 
int A000330( int x ) {
  return 1LL * x * ( x + 1 ) % MOD * ( 2 * x + 1 ) % MOD * inv( 6 ) % MOD;
}
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  long long ans = 0;
  for( int m = 1; 1LL * m * m <= N; ++m ) { // A143127
    ( ans += 1LL * m * ( ( m + N / m ) % MOD ) % MOD * ( ( N / m + 1 - m ) % MOD ) % MOD ) %= MOD;
  }
  ans -= A000330( floor( sqrt( N ) ) ) % MOD;
  if( ans < 0 ) ans += MOD;
  cout << ans << endl;
  return 0;
}