发现这个等比数列的公比可能是一个分数.所以考虑对a进行质因数分解,然后枚举公比.因为公比两项是平方级别,所以这个枚举公比大概是log级别.
复杂度比较玄学,AI说是 $O(n\log\log n)$ ,瓶颈在于欧拉筛,反正能过.
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
69
70
71
72
73
74
75
76
77
78
79
int   vis[100000010];//存最小质因数,负的表示质数表中的位置(负的)
int  p[10000010],ptop=0;//存质数 
void sieve(int n){//[1,n]
	int tmp;
	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;
			}else{
			}
		}
	}
}

int st[1000],top=0;
int sst[1000],ttop=0;
i64 ssst[1000000],tttop=0;
void dfs(int num,i64 prod){
	if(num>ttop){
		// si
		ssst[++tttop]=prod;
		return;
	}
	dfs(num+1,prod);
	dfs(num+1,prod*sst[num]);
}
vector<int>ck(int num){
	top=0;ttop=0;tttop=0;
	while(vis[num]>0){
		st[++top]=vis[num];
		num/=vis[num];
	}
	if(num!=1){
		st[++top]=num;
	}
	sort(st+1,st+top+1);
	for(int i=1;i<top;++i){
		if(st[i]==st[i+1]){
			sst[++ttop]=st[i];
			i++;
		}
	}
	vector<int>res;
	dfs(1,1);
	sort(ssst+1,ssst+tttop+1);
	tttop=unique(ssst+1,ssst+tttop+1)-ssst-1;
	for(int i=1;i<=tttop;++i){
		res.push_back(ssst[i]);
	}
	return res;
}

long long n,m,res;
//#define NaraFluorine
int main(){
	fin>>n;
	sieve(n);
	si;
	fout.flush();
	n++;
	for(int i=1;i<=ptop;++i){
		auto tmp=ck(p[i]+1);
		for(auto il:tmp){
			for(i64 j=il+1;(p[i]+1)/il/il*j*j<=n;++j){
				if(__gcd(j,(i64)il)!=1)continue;
				if(vis[(p[i]+1)/il/il*j*j-1]<0&&vis[(p[i]+1)/il*j-1]<0){
					res+=p[i]+(p[i]+1)/il*j-1+(p[i]+1)/il/il*j*j-1;
				}
			}
		}
	}
	fout<<res;
	return 0;
}