#include<map>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
#define pb push_back
#define IT iterator
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=1e6+10,size=1<<20,mod=1e9+7,inv=(mod+1)/2;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

//math
ll mult(ll a,ll b,ll p) {
	a=(a%p+p)%p; b=(b%p+p)%p;
	ll c=(ld)a*b/p;
	return a*b-c*p;
}
ll gcd(ll a,ll b) {return !a?b:gcd(b%a,a);}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
ll power(ll a,ll b=mod-2) {
	ll c=1;
	while(b) {
		if(b&1) c=c*a%mod;
		b /= 2; a=a*a%mod;
	}
	return c;
}
ll Power(ll a,ll b=mod-2) {
	ll c=1;
	while(b) {
		if(b&1) c=mult(c,a,mod);
		b /= 2; a=mult(a,a,mod);
	}
	return c;
}

int prime[N],tot,mu[N],g[N]; bool v[N];
void upd(int &x) {x-=(x>=mod)*mod; x+=x>>31&mod;}

void get(int x) {
	mu[1]=1;
	for(int i=2;i<=x;i++) {
		if(!v[i]) prime[++tot]=i,mu[i]=-1;
		for(int j=1,k;(k=i*prime[j])<=x;j++) {
			v[k]=1;
			if(i%prime[j]) mu[k]=-mu[i];
			else break;
		}
	}
	for(int i=1;i<=x;i++) {
		upd(mu[i]=mu[i-1]+mu[i]*i);
		for(int j=i;j<=x;j+=i) upd(g[j]+=i);
	}
	for(int i=1;i<=x;i++) upd(g[i]+=g[i-1]);
}

ll calc(ll n) {
	if(n<N) return g[n];
	ll s=0;
	for(ll l=1,r;l<=n;l=++r) {
		r=n/(n/l);
		s+= (r-l+1)%mod*((r+l)%mod)%mod*inv%mod*((n/l)%mod)%mod;
	}
	return s%mod;
}

int main() {
	get(N-1);
	int _;qr(_); while(_--) {
		ll n,ans=0;qr(n);
		for(ll l=1,r;l*l<=n;l=++r) {
			r=l;
			while(n/(r+1)/(r+1)==n/l/l) ++r;
			ans += (mu[r]-mu[l-1]+mod) * calc(n/l/l) % mod;
		}
		pr2(ans%mod);
	}
	return 0;
}

这里 说是$O(\sqrt n \log n)$的.

我不是很明白$calc$在每组数据的复杂度.....

望得到大佬解答