Solution - P1447 [NOI2010] 能量采集

Posted on Edited on

P1447 [NOI2010] 能量采集

idea:

数论

解决方案：

如果莫比乌斯反演是正解的话，这道题是最善良的莫反练习题了。。。感觉比很多蓝题都简单。

首先观察答案：

∑i=1n∑j=1m((2⋅(gcd⁡(i,j)−1)+1)\sum_{i=1}^n\sum_{j=1}^m((2\cdot(\gcd(i,j)-1)+1)

化简为：

2⋅∑i=1n∑j=1mgcd⁡(i,j)  −n⋅m2\cdot\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\ \ -n\cdot m

∑i=1n∑j=1mgcd⁡(i,j)\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j) 这个式子再熟悉不过了，爱怎么化简怎么化简。

本题我用的是以下这个式子：

∑d=1nd∑k=1⌊nd⌋μ(k)⋅⌊nk⋅d⌋⋅⌊mk⋅d⌋\sum_{d=1}^n d\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor} \mu(k)\cdot \lfloor \frac{n}{k\cdot d}\rfloor\cdot \lfloor \frac{m}{k\cdot d}\rfloor

两个整数分块，复杂度 O(max(n,m))O(max(n,m)) 。

如果多种询问的话，还可以做到 O(T⋅max⁡(n,m)+max⁡(n,m)log⁡max⁡(n,m))O(T\cdot \sqrt{\max(n,m)}+\max(n,m)\log \max(n,m)) ，用以下这个式子：

∑T=1n⌊nT⌋⋅⌊mT⌋∑d∣Td∑k∣Tμ(k)\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor\sum_{d\mid T} d\sum_{k\mid T} \mu(k)

第一种方法 CODECODE :

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
#include<bits/stdc++.h>
#define F(i,x,y) for(int i=x;i<=y;++i)
#define int long long 
using namespace std;typedef long long LL;
const int N=1e5+5;
int n,m,mu[N],p[N],idx;LL ans;bool vis[N];
inline void INIT(){
	mu[1]=1;F(i,2,n){
		if (!vis[i]) mu[i]=-1,p[++idx]=i;
		for (int j=1;p[j]*i<=n;++j){
			vis[p[j]*i]=1;
			if (i%p[j]==0){
				mu[p[j]*i]=0;break;
			}mu[p[j]*i]=-mu[i];
		}
	}
	F(i,2,n) mu[i]=mu[i-1]+mu[i];
}
inline LL cal(LL a,LL b){
	LL res=0;int l=1;while (l<=a){
		int r=min(a/(a/l),b/(b/l));
		res+=(LL)(mu[r]-mu[l-1])*(a/l)*(b/l);
		l=r+1;
	}
	return res;
}
signed main(){
	cin>>n>>m;if (n>m) n^=m^=n^=m;INIT();
	int l=1;while (l<=n){
		int r=min(n/(n/l),m/(m/l));
		ans+=(LL)(l+r)*(r-l+1)/2*cal(n/l,m/l);
		l=r+1;
	}
	cout<<ans*2-n*m<<endl;
	return 0;
}