记录编号	587510	评测结果	AAAAA
题目名称	平方前缀和	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.596 s
提交时间	2024-04-04 00:06:57	内存使用	67.72 MiB

#include <bits/stdc++.h>
using namespace std;
//杜教筛 
#define ll long long
const int N = 5e6+10;
const ll mod = 1e9+7,inv6 = 166666668,inv2 = 500000004,m = 5e6;
ll n;
int p[N],cnt;
ll f[N];
bool v[N];
unordered_map<ll,ll>sumf;
void get(){
	f[1] = 1;
	for(int i = 2;i <= m;i++){
		if(!v[i])p[++cnt] = i,f[i] = i - 1;
		for(int j = 1;j <= cnt && i <= m / p[j];j++){
			v[i*p[j]] = 1;
			if(i % p[j] == 0){
				f[i*p[j]] = f[i] * (ll)p[j] % mod;break;
			}
			f[i*p[j]] = f[i] * (ll)(p[j] - 1) % mod;
		}
	}
	for(int i = 1;i <= m;i++)f[i] = (f[i] * (ll)i % mod + f[i-1]) % mod;
}
ll s(ll l,ll r){
	return ((l + r) * (r - l + 1ll) / 2ll) % mod;
}
ll S(ll x){
	if(x <= m)return f[x];
	if(sumf[x])return sumf[x];
	ll sum = (((x + 1) * (2ll * x + 1ll)) % (mod * 6) * x / 6) % mod;//??
	for(ll l = 2ll,r;l <= x;l = r + 1ll){
		r = min(x,x / (x / l));
		sum = ((sum - (s(l,r) * S(x / l) % mod)) % mod + mod) % mod;
	}
	return sumf[x] = sum;
}
int main(){
	freopen("squaresum.in","r",stdin);
	freopen("squaresum.out","w",stdout);
	get();
	scanf("%lld",&n);//(φ・id) * id = id ^ 2 
	printf("%lld\n",S(n));
 
	return 0;
	
}