「51nod 2026」Gcd and Lcm

发表于

已知 f(x)=∑d∣xμ(d)⋅df(x)=\sum_{d|x} \mu(d) \cdot d ，现在请求出下面式子的值：

∑i=1n∑j=1nf(gcd⁡(i,j))⋅f(lcm(i,j))\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(\gcd(i,j)) \cdot f(\text{lcm}(i,j))

由于值可能过大所以请对 109+710^9+7 取模

Constraints

$ n \leq 10^9 $

Solution

对 ii 和 jj 进行质因数分解，即 i=∏pqii=\prod p^{qi} ，j=∏pqjj=\prod p^{qj} ，可以得到：

    f(gcd⁡(i,j))⋅f(lcm(i,j))=∏f(pmin(qi,qj))⋅f(pmax(qi,qj))=f(i)⋅f(j)\begin{aligned} &~~~~f(\gcd(i,j)) \cdot f(\text{lcm}(i,j)) \\ &= \prod f(p^{min(qi,qj)})\cdot f(p^{max(qi,qj)}) \\ &= f(i)\cdot f(j) \end{aligned}

将原答案转换为：

ans=∑i=1n∑j=1nf(gcd⁡(i,j))⋅f(lcm(i,j))=∑i=1n∑j=1nf(i)⋅f(j)=(∑i=1nf(i))2=(∑i=1n∑d∣iμ(d)⋅d)2=(∑i=1nμ(i)⋅i⋅⌊ni⌋)2\begin{aligned} ans&=\sum_{i=1}^n \sum_{j=1}^n f(\gcd(i,j)) \cdot f(\text{lcm}(i,j)) \\ &=\sum_{i=1}^n \sum_{j=1}^n f(i)\cdot f(j) \\ &=(\sum_{i=1}^n f(i))^2 \\ &=(\sum_{i=1}^n \sum_{d|i} \mu(d) \cdot d)^2 \\ &=(\sum_{i=1}^n \mu(i) \cdot i \cdot \left \lfloor \frac{n}{i} \right \rfloor)^2 \end{aligned}

然后令 S(n)=∑i=1nμ(i)⋅iS(n)=\sum_{i=1}^n \mu(i) \cdot i ，则由以下推导：

1=∑i=1ni⋅∑j∣iμ(j)=∑i=1ni⋅∑j=1⌊ni⌋j⋅μ(j)=∑i=1ni⋅S(⌊ni⌋)\begin{aligned} 1&=\sum_{i=1}^n i \cdot \sum _{j|i} \mu(j) \\ &=\sum_{i=1}^n i\cdot \sum_{j=1}^{\left \lfloor \frac{n}{i} \right \rfloor} j \cdot \mu(j) \\ &=\sum_{i=1}^n i\cdot S({\left \lfloor \frac{n}{i} \right \rfloor}) \end{aligned}

可得：S(n)=1−∑i=2ni⋅S(⌊ni⌋)S(n)=1-\sum_{i=2}^n i\cdot S({\left \lfloor \frac{n}{i} \right \rfloor})

杜教筛即可。

Code

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
49
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e6;
const int mod=1e9+7;
int n,nn,tot,now;
int miu[N+5],pri[N+5],a[N+5];
bool np[N+5];
int calc(int l,int r){return 1ll*(l+r)*(r-l+1)/2%mod;}
int solve(int n)
{
	if(n<=N)return miu[n];
	if(~a[nn/n])return a[nn/n];
	int ans=1,pos;
	for(int i=2;i<=n;i=pos+1)
	{
		pos=n/(n/i);
		ans=(ans-1ll*calc(i,pos)*solve(n/i)%mod+mod)%mod;
	}
	return a[nn/n]=ans;
}
int main()
{
	scanf("%d",&n);
	nn=n;miu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!np[i]){miu[i]=-1;pri[++tot]=i;}
		for(int j=1;1ll*i*pri[j]<=N;j++)
		{
			now=i*pri[j];np[now]=true;
			if(i%pri[j]==0){miu[now]=0;break;}
			miu[now]=-miu[i];
		}
	}
	for(int i=1;i<=N;i++)
		miu[i]=(miu[i-1]+(1ll*miu[i]*i%mod+mod)%mod)%mod;
	int ans=0,pos;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i=pos+1)
	{
		pos=n/(n/i);
		ans=(ans+1ll*(solve(pos)-solve(i-1)+mod)%mod*(n/i)%mod)%mod; 
	}
	printf("%lld",1ll*ans*ans%mod);
	return 0;
}