洛谷P2522 [HAOI2011]Problem b (莫比乌斯反演+容斥)
2024-09-05 14:55:13
题意:求$\sum_{i=a}^{b}\sum_{j=c}^{d}[gcd(i,j)==k]$(1<=a,b,c,d,k<=50000)。
是洛谷P3455 [POI2007]ZAP-Queries加强版,多了下界。
设$f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==k]$
根据容斥可以显然的得出Ans=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)。
对于f(n,m)的求解:
$f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==k]$
$=\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}[gcd(i,j)==1]$
$=\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d){\lfloor \frac{n}{kd}\rfloor}{\lfloor \frac{m}{kd}\rfloor}$
预处理莫比乌斯函数前缀和,后面整除分块。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
bool p[N];
int pri[N],tot,mu[N];
void init() {
mu[]=;
for(int i=;i<N;i++) {
if(!p[i]) pri[tot++]=i,mu[i]=-;
for(int j=;j<tot&&pri[j]*i<N;j++) {
p[pri[j]*i]=true;
if(i%pri[j]==) {
mu[i*pri[j]]=;
break;
}
else mu[i*pri[j]]=-mu[i];
}
}
for(int i=;i<N;i++) mu[i]+=mu[i-];
}
ll cal(int n,int m,int k) {
if(n>m) swap(n,m);
ll ans=;
for(int l=,r;l<=n;l=r+) {
r=min(n/(n/l),m/(m/l));
ans+=1LL*(mu[r]-mu[l-])*(n/k/l)*(m/k/l);
}
return ans;
}
int main() {
init();
int T,a,b,c,d,k;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%lld\n",cal(b,d,k)-cal(b,c-,k)-cal(a-,d,k)+cal(a-,c-,k));
}
return ;
}
最新文章
- php new self()和new static()
- centos7
- C# 中 多线程同步退出方案 CancellationTokenSource
- [转载]TFS与Project、Excel同步
- html5学习笔记6-- canvas
- 基于LeNet网络的中文验证码识别
- Scala access modifiers and qualifiers in detail
- 使用C语言描述静态链表和动态链表
- 由IP和掩码计算广播地址
- Memcached内存分配优化及使用问题
- Android的事件处理机制详解(二)-----基于监听的事件处理机制
- 基于MFC与第三方类CWebPage的百度地图API开发范例
- Oracle与mysql的字段类型整理
- 浅谈卷积神经网络及matlab实现
- 用过的关于css的知识
- C# 一个初学者对 依赖注入 IOC 的理解( 含 Unity 的使用)
- Vue学习笔记一:初识Vue
- apply,all,bind的区别
- 我的python渗透测试工具之主机嗅探
- spring cloud(一)带你进入分布式