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++)  //枚举第一项
	{
        if (a*a > N / a) break; //后面两项都大于第一项
        for (ll b = a; b <= N; b++)  //第二项
		{
            ll cma = N / (a * b);
            if (cma < b) break;
            ans += cma - b + 1;
        }
            
    }
    cout << ans << endl;
}