AtCoder—C - ABC conjecture

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

You are given a positive integer NN.

Find the number of triples of positive integers (A, B, C)(A,B,C) such that A\leq B\leq CA≤B≤C and ABC\leq NABC≤N.

The Constraints guarantee that the answer is less than 2^{63}263.

Constraints

• 1 \leq N \leq 10^{11}1≤N≤1011
• NN is an integer.

Input

Input is given from Standard Input in the following format:

NN

Output

Print the answer.

Sample Input 1 Copy

Copy

4

Sample Output 1 Copy

Copy

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2)(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2 Copy

Copy

100

Sample Output 2 Copy

Copy

323

Sample Input 3 Copy

Copy

100000000000

Sample Output 3 Copy

Copy

5745290566750

#include #include #include using namespace std;typedef long long ll;signed main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll N;cin >> N;ll ans = 0;for (ll a = 1; a <= N; a++) //enumerate the first item{if (a*a > N / a) break; //The last two items are greater than the first itemfor (ll b = a; b <= N; b++) //Second item{ll cma = N / (a ​​* b);if (cma < b) break;ans += cma - b + 1;}}cout << ans << endl;}