Monthly Training Farm - May 2017 C. factor1 ( Math, Sqrt Decomposition )

Problem Description:
Given A, B, print number of positive factors of all values between integer in [ A, B ].

Constraints:
1 ≤ A ≤ B ≤ 1e14

Solution:
Consider calculating result of [ 1, B ] - [ 1, A - 1 ].
It uses similar technique of this.
Simply put, to find number of positive factors in range [ 1, N ], we enumerate factors up to N ** 0.5, then enumerate groups of factors with contribution ( number of values with that factor ) of less than N ** 0.5.

Time Complexity:
O( B ** 0.5 )

#include <bits/stdc++.h>
using namespace std;

long long A, B;

long long solve( long long n ) {
  long long res = 0;
  int sn;
  for( int i = 1; 1LL * i * i <= n; ++i ) {
    res += n / i;
    sn = i;
  }
  for( int f = n / ( sn + 1 ); f; --f ) {
    res += 1LL * f * ( n / f - n / ( f + 1 ) );
  }
  return res;
}

signed main() {
  cin >> A >> B;
  cout << solve( B ) - solve( A - 1 ) << endl;
  return 0;
}