整理一下题干,一个质数在满立方数中要么不出现.要么出现3次及以上.
找几个很小的质数的三次方测以下,发现这样的数的质因数不会超过7个.
同时对于一个满立方数,贡献是 $lim/x$ .
所以我们预处理 $\sqrt[3]{n}$ 以内的质数,然后用一个栈表示当前可以被拓展的数字集合,然后又一个栈表示所有在当前付过p3代价的数,他们可以随意乘p了.最后这两个栈合并,然后再筛掉一些特别大以至于不能拓展的数(0.1572s).
exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
fastio::IN fin;
fastio::OUT fout;
int   vis[1000010];
i128  p[100010],ptop=0;
void sieve(int n){//[1,n]
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			vis[i]=-(++ptop);
			p[ptop]=i;
		}
		for(int j=1;j<=ptop&&i*p[j]<=n;++j){
			vis[i*p[j]]=p[j];
			if(i%p[j]==0){
				break;
			}
		}
	}
}
i128 p3[1000000];

i64 lim=1e18;
i128 res=0;

i128 st[10000000],top=0;
i128 pre[1000000],prtop=0;

long long n,m;
//#define NaraFluorine
int main(){
	sieve(1000000);
	for(int i=1;i<=ptop;++i){
		p3[i]=p[i]*p[i]*p[i];
	}
	for(int i=1;i<=ptop;++i){
		prtop=0;
		pre[++prtop]=p3[i];
		while(pre[prtop]*p[i]<=lim){
			prtop++;
			pre[prtop]=pre[prtop-1]*p[i];
		}
		for(int j=1;j<=top;++j){
			if(st[j]*p3[i]>lim)continue;
			pre[++prtop]=st[j]*p3[i];
			while(pre[prtop]*p[i]<=lim){
				prtop++;
				pre[prtop]=pre[prtop-1]*p[i];
			}
		}
		for(int j=1;j<=prtop;++j){
			st[++top]=pre[j];
		}
		prtop=0;
		for(int j=1;j<=top;++j){
			if(st[j]*p3[i]>lim){
				res+=lim/st[j];
			}else{
				st[++prtop]=st[j];
			}
		}
		top=prtop;
	}
	for(int i=1;i<=top;++i){
		res+=lim/st[i];
	}
	res+=lim;
	fout<<res<<"\n";
	return 0;
}