题目描述


题目分析

暴力遍历 i、j 求和,肯定会超时。
我们换一个角度求 $gcd(i,j)==d\ (i,j \in [1,n])$ 的对数 count(d),则 $ans=\sum{count(d)*d^2}$
求 $gcd(i,j)==d\ (i,j \in [1,n])$ 的对数可以转换为求 $gcd(i,j)==1\ (i,j \in [1,n/d])$ 的对数,既求互质的 i、j 的对数,可以使用欧拉函数,
欧拉函数 $\varphi(n)$ 是小于或等于 n 的正整数中与 n 互质的数的数目,欧拉函数可以通过欧拉线性筛打表得到。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
using namespace std;
const int N=1e7+1,MOD=1e9+7;
typedef long long ll;

int vis[N];
ll prime[N];
ll phi[N];
ll s[N];

void Euler(int n) {
phi[1]=1;
int cnt=0;
for(int i=2;i<=n;i++) {
if(!vis[i]) {
prime[cnt++]=i;
phi[i]=i-1; //若a为素数,phi[a]=a-1
}
for(int j=0;j<cnt&&i*prime[j]<=n;j++) { //用当前已得到的素数数组筛去i*prime[j]
vis[i*prime[j]]=1; //i*prime[j]不是素数
if(i%prime[j]==0) {
phi[prime[j]*i]=phi[i]*prime[j]; //若a为素数,b%a==0,则phi[a*b]=phi[b]*a
break;
}
else {
phi[prime[j]*i]=phi[i]*(prime[j]-1); //若a为素数,b%a!=0,则phi[a*b]=phi[b]*phi[a]=phi[b]*(a-1)
}
}
}
s[1]=phi[1];
for(int i=2;i<=n;i++) {
s[i]=s[i-1]+2*phi[i];
}
}

int main()
{
int n;
cin>>n;
Euler(n);
ll sum=0;
for(int i=1;i<=n;i++) {
sum=(sum+s[n/i]%MOD*i%MOD*i%MOD)%MOD;
}
cout<<sum<<endl;

return 0;
}