分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。
然后对于求这样单个的gcd(x,y)=k的,我们通常采用莫比乌斯反演
但是,时间复杂度是O(n*(n/k))的,当复杂度很坏的时候,当k=1时,退化到O(n^2),超时
然后进行分块优化,时间复杂度是O(n*sqrt(n))
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=5e4+;
const int INF=0x3f3f3f3f;
bool vis[N];
int prime[N],mu[N],cnt;
void getmu()
{
mu[] = ;
for(int i=; i<=N-; i++)
{
if(!vis[i])
{
prime[++cnt] = i;
mu[i] = -;
}
for(int j=; j<=cnt&&i*prime[j]<=N-; j++)
{
vis[i*prime[j]] = ;
if(i%prime[j]) mu[i*prime[j]] = -mu[i];
else
{
mu[i*prime[j]] = ;
break;
}
}
}
}
LL solve(int n,int m,int k){
n/=k,m/=k;
int l=min(n,m);
LL ans=;
for(int i=,j;i<=l;i=j+){
j=min(n/(n/i),m/(m/i));
ans+=1ll*(mu[j]-mu[i-])*(n/i)*(m/i);
}
return ans;
}
int main(){
getmu();
for(int i=;i<=N-;++i)mu[i]+=mu[i-];
int T;
scanf("%d",&T);
while(T--){
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%lld\n",solve(b,d,k)-solve(b,c-,k)-solve(a-,d,k)+solve(a-,c-,k));
}
return ;
}
BZOJ2301: [HAOI2011]Problem b 莫比乌斯反演的更多相关文章
-
BZOJ2301: [HAOI2011]Problem b[莫比乌斯反演 容斥原理]【学习笔记】
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MBSubmit: 4032 Solved: 1817[Submit] ...
-
[bzoj2301][HAOI2011]Problem B —— 莫比乌斯反演+容斥原理
题意 给定a, b, c, d, k,求出: \[\sum_{i=a}^b\sum_{j=c}^d[gcd(i, j) = k]\] 题解 为方便表述,我们设 \[calc(\alpha, \beta ...
-
BZOJ2301:[HAOI2011]Problem b(莫比乌斯反演,容斥)
Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数 ...
-
[BZOJ1101&;BZOJ2301][POI2007]Zap [HAOI2011]Problem b|莫比乌斯反演
对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d. 我们可以令F[n]=使得n|(x,y)的数对(x,y)个数 这个很容易得到,只需要让x, ...
-
P2522 [HAOI2011]Problem b (莫比乌斯反演)
题目 P2522 [HAOI2011]Problem b 解析: 具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是,这个题求的是\(\sum_{i=a}^b\sum_{j= ...
-
Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...
-
BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MBSubmit: 1007 Solved: 415[Submit][ ...
-
BZOJ.2301.[HAOI2011]Problem B(莫比乌斯反演 容斥)
[Update] 我好像现在都看不懂我当时在写什么了=-= \(Description\) 求\(\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]\) \(Solution\) 首先 ...
-
[POI2007]ZAP-Queries &;&; [HAOI2011]Problem b 莫比乌斯反演
1,[POI2007]ZAP-Queries ---题面---题解: 首先列出式子:$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$ ...
随机推荐
-
java mvc web 项目web.xml头改错了,死活加载不上springMvc的jar
Description Resource Path Location TypeOne or more constraints have not been satisfied. ...
-
BCB 多线程的同步与协调
多线程编程是提高系统资源利用率的一种常见方式.它占用的资源更小,启动更快,还可以实现在后台运行一些需时较长的操作.[喝小酒的网摘]http://blog.hehehehehe.cn/a/8498.ht ...
-
__cdecl __stdcall __fastcall之函数调用约定讲解
首先讲解一下栈帧的概念: 从逻辑上讲,栈帧就是一个函数执行的环境:函数参数.函数的局部变量.函数执行完后返回到哪里等等. 实现上有硬件方式和软件方式(有些体系不支持硬件栈) 首先应该明白,栈是从高地址 ...
-
IOS 后台执行
在IOS后台执行是本文要介绍的内容,大多数应用程序进入后台状态不久后转入暂停状态.在这种状态下,应用程序不执行任何代码,并有可能在任意时候从内存中删除.应用程序提供特定的服务,用户可以请求后台执行时间 ...
-
VM Depot 喜迎中国本土开源镜像!
发布于 2014-04-07 作者 陈 忠岳 VM Depot 登陆中国之际,我非常高兴地告诉大家,一批各位耳熟能详的中国本地开源镜像已同时上线!得益于开源社区的大力支持,Ubuntu 麒麟13 ...
-
如何在hadoop中控制map的个数
hadooop提供了一个设置map个数的参数mapred.map.tasks,我们可以通过这个参数来控制map的个数.但是通过这种方式设置map的个数,并不是每次都有效的.原因是mapred.map. ...
-
ubuntu16.04无法设置选择wifi的解决办法
在公司上班一直连接的有线,直到昨天拿回家才发现ubuntu无法选择使用wifi上网,这让人非常无奈,截图类似如下: 而正常情况下我们应该在启用联网的下面有wifi链接的选项,如图: 我隐约猜测是和驱动 ...
-
system()、exec()、fork()三个与进程有关的函数的比较
启动新进程(system函数) system()函数可以启动一个新的进程. int system (const char *string ) 这个函数的效果就相当于执行sh –c string. 一般 ...
-
vs code 操作Git
首次从Git拉取项目:Ctrl+Shift+p 选择Git 克隆 拉取成功后 Ctrl+波浪号进入控制台选择终端 使用npm install下载依赖 到此就从Git拉取成功了: 如果提示npm错误,有 ...
-
Linux 修改时间和时区为上海时区
发现centos7的时间是utc的,和上海时间不一样. 由于/usr/share/zoneinfo/Asia/ 这个目录下没有北京时区,就选择了上海时区,只要赋值过去就可以了 rm -f /etc/ ...