BZOJ2005 [NOI2010] 能量采集

starli posted @ 2016年1月24日 20:11 in 数学 , 152 阅读

这题就是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)$

我们考虑枚举k使 gcd(i,j)=k

定义 g[k]表示以k为公约数的i,j有多少对,f[k]表示以k为最大公约数的i,j有多少对

首先我们想k是若干个数的公约数(非最大) 那么  g[k]=(n/k)*(m/k)

而以k为最大公约数的时候 要用g[k]减掉 f[2k],f[3k],f[4k]...于是 $f[k]=g[k]-\sum_{i=1}^{i*k<=min(n,m)}f[i*k]$

最后求一下和就好了

下面是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
LL f[N],n,m,mx,ans;
int main(){
	//freopen("2005.in","r",stdin);freopen("2005.out","w",stdout);
	scanf("%lld%lld",&n,&m);mx=min(n,m);
	for(int i=1;i<=mx;i++) f[i]=(n/i)*(m/i);
	for(int i=mx;i>=1;i--) 
		for(int j=2;j*i<=mx;j++) f[i]-=f[j*i];
	for(int i=1;i<=mx;i++) ans+=(i*2-1)*f[i];
	printf("%lld",ans);
	return 0;
}


 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter