题解

$a,b$ 暴力for，然后我们注意到通过 $a,b$ 可以求到 $c$ 的范围，二分就行

#include <iostream>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
bitset <1000005> vis;
vector <int> p; 
void sieve(int n){
	for(int i = 2; i * i <= n; i++){
		if(!vis[i]){
			for(int j = i << 1; j <= n; j += i){
				vis[j] = 1;
			}
		}
	}
	for(int i = 2; i <= n; i++){
		if(!vis[i]) p.push_back(i);
	}
}
signed main(){
	sieve(1000000);
	int n;
	cin >> n;
	int ct = 0;
	for(int i = 0; i < p.size() && p[i] * p[i] * p[i] <= n; i++){
		for(int j = i + 1; j < p.size() && p[i] * p[i] * p[j] <= n; j++){
			int l = 0, r = p.size() - 1, val = n / (p[i] * p[i] * p[j]);
			if(p[j] * p[j] > val) break;
			while(l <= r){
				int mid = (l + r) >> 1;
				if(p[mid] * p[mid] > val) r = mid - 1;
				else l = mid + 1;
			}
			ct += r - j;
		}
	}
	cout << ct;

	return 0;
}

时间复杂度：$O((\sqrt[3] n)^2\log n)$.