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
| #include<cstdio>
#include<math.h>
using namespace std;
#define ll long long
const int N = 1000005;
int T, sn, id, cnt, prime[N];
ll n, g[N<<1], a[N<<1];
inline int Id(ll x){ return x<=sn?x:id-(n/x)+1;}
ll S(ll a, int b){
if(a<prime[b]) return 0;
ll ans=g[Id(a)]-(b-1)*3;
for(int i=b, lim=sqrt(a); i<=cnt && prime[i]<=lim; ++i){
ans+=S(a/prime[i], i+1)*3+5;
for(ll x=(ll)prime[i]*prime[i], j=5; x*prime[i]<=a; x*=prime[i], j+=2)
ans+=S(a/x, i+1)*j+j+2;
}
return ans;
}
int main() {
scanf("%d", &T);
while(T--){
scanf("%lld", &n), sn=sqrt(n);
cnt=id=0;
for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=(a[id]-1)*3;
for(int i=2; i<=sn; ++i) if(g[i]!=g[i-1]){
prime[++cnt]=i;
ll lim=(ll)i*i;
for(int j=id; a[j]>=lim; --j) g[j]-=g[Id(a[j]/i)]-(cnt-1)*3;
}
printf("%lld\n", S(n, 1)+1);
}
return 0;
}
|