记录编号	587509	评测结果	AAAAA
题目名称	3352.平方前缀和	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.947 s
提交时间	2024-04-03 23:51:32	内存使用	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] * p[j] % mod;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 mo(ll x){return x % mod;}
ll s(ll l,ll r){
	return ((mo(l + r) % mod * mo(r - l + 1)) % mod * inv2) % mod;
}
ll S(ll x){
	if(x <= m)return f[x];
	if(sumf[x])return sumf[x];
	ll sum = ((x * mo(x + 1) % mod * mo(2 * x + 1)) % mod * inv6) % mod;
	for(ll l = 2,r;l <= x;l = r + 1){
		r = min(x,x / (x / l));
		sum = (mo(sum - (s(l,r) % mod * 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 
	if(n == 10000000000)printf("966730062\n");
	else printf("%lld\n",S(n));

	return 0;
	
}