记录编号	587506	评测结果	AATAT
题目名称	3352.平方前缀和	最终得分	60
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	3.039 s
提交时间	2024-04-03 23:12:15	内存使用	67.83 MiB

#include <bits/stdc++.h>
using namespace std;
//杜教筛 
#define ll long long
#define m 1
const int N = 5e6+10;
const ll mod = 1e9+7,inv6 = 166666668,inv2 = 500000004;
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] * p[j];break;
			}
			f[i*p[j]] = f[i] * (p[j] - 1) % mod;
		}
	}
	for(int i = 1;i <= m;i++)f[i] = (f[i] * i % mod + f[i-1]) % mod;
}
ll s(ll l,ll r){
	return (l + r) * (r - l + 1) % mod * inv2 % mod;
}
ll S(ll x){
	if(x <= m)return f[x];
	if(sumf.count(x))return sumf[x];
	ll sum = x * (x + 1) % mod * (x<<1|1) % mod * inv6 % mod;
	for(ll l = 2,r;l <= x;l = r + 1){
		r = min(x,x / (x / l));
		sum = ((sum - (s(l,r) * S(x / l))) % 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;
	
}