BZOJ3994 [SDOI2015]约数个数和

题面

设$f(x)$为x的约数个数,给定$N$、$M$,求$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i j)$

思路

推导过程

有个定理$f(ij)=\sum_{x | i} \sum_{y | j}[g c d(x, y)=1]$。你问我如何推导,我只能告诉你无可奉告——这里纸太小,写不下。

然后大力推导以后数论分块即可,但是要预处理所有$x$的$\sum_{i=1}^{x}\left\lfloor\frac{x}{i}\right\rfloor$,这个$nsqrt(n)$的除法分块就可以轻松解决了,然后线性筛后对于答案做一次除法分块即可。

代码

#include<bits/stdc++.h>
#define Maxn 50000
using namespace std;
long long T,N,M,mu[Maxn<<1],cnt=0,prime[Maxn<<1],sum_mu[Maxn<<1],g[Maxn<<1],r=0,ans=0;
bool is_prime[Maxn<<1];
int main()
{       
	for (long long i=1;i<=Maxn;i++)
	{
		for (long long l=1;l<=i;l=r+1)
		{
			r=i/(i/l);
			g[i]+=(r-l+1)*(i/l);
		}
	}
	mu[1]=1;sum_mu[1]=1;
	for (long long i=2;i<=Maxn;i++)
	{   
		if (!is_prime[i]) prime[++cnt]=i,mu[i]=-1;
		for (long long j=1;j<=cnt&&i*prime[j]<=Maxn;j++)
		{
			is_prime[i*prime[j]]=1;
			mu[i*prime[j]]=-mu[i];
			if (!(i%prime[j])){mu[i*prime[j]]=0;break;}
		}  
		sum_mu[i]=sum_mu[i-1]+mu[i];
	}   
	r=0;
	cin>>T;
	while (T--)
	{
		ans=0;
		cin>>N>>M;
		for (long long l=1;l<=min(N,M);l=r+1)   
		{
			r=min(N/(N/l),M/(M/l));
			ans+=(sum_mu[r]-sum_mu[l-1])*g[N/l]*g[M/l]; 
		}
		cout<<ans<<endl;
	}
	return 0;
}       
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇