传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2301
很好的一道题。首先把每个询问转化为4个子询问,最后的结果就是这四个子询问的记过加加减减,类似二维前缀和。那么问题转化为在1 <= x <= lmtx, 1 <= y <= lmty时gcd(x, y) == k的对数,这个问题在转化一下,转化成1 <= x <= lmtx / k,1 <= y <= lmty / k时x与y互质的对数。莫比乌斯反演一下,就有了,但是会TLE,所以需要分块优化。
其它博客讲得很清楚了,程序精华在15~16行。
#include <cstdio>
#include <algorithm> const int maxn = 50005; int n, a, b, c, d, k, mu[maxn] = {0, 1}, prime[maxn], tot, s[maxn];
char book[maxn]; inline long long slove(int lmtx, int lmty) {
lmtx /= k;
lmty /= k;
int lmt = std::min(lmtx, lmty), last;
long long rt = 0;
for (int i = 1; i <= lmt; i = last + 1) {
last = std::min(lmtx / (lmtx / i), lmty / (lmty / i));
rt += (long long)(lmtx / i) * (lmty / i) * (s[last] - s[i - 1]);
}
return rt;
} int main(void) {
scanf("%d", &n);
for (int i = 2; i < maxn; ++i) {
if (!book[i]) {
prime[tot++] = i;
mu[i] = -1;
}
for (int j = 0; j < tot; ++j) {
if (i * prime[j] > maxn) {
break;
}
book[i * prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
else {
mu[i * prime[j]] = -mu[i];
}
}
}
for (int i = 1; i < maxn; ++i) {
s[i] = s[i - 1] + mu[i];
}
while (n--) {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
printf("%lld\n", slove(b, d) - slove(a - 1, d) - slove(b, c - 1) + slove(a - 1, c - 1));
}
return 0;
}
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 莫比乌斯反演
分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 然后对于求这样单个的gcd(x,y)=k的, ...
-
[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 第一行一个整数 ...
-
Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...
-
[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 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]$$ ...
随机推荐
-
content相关属性
content属性值 : width:可视区域的宽度,值可为数字或关键词device-width height:同width intial-scale:页面首次被显示是可 ...
-
java.lang.Class.forName(String name, boolean initialize, ClassLoader loader)方法
描述 Java.lang.Class.forName(String name, boolean initialize, ClassLoader loader) 方法返回与给定字符串名的类或接口的Cla ...
-
python学习笔记系列----(四)模块
这一章主要是叙述了python模块的概念以及包的概念,还有它们的使用:收获也是大大的. 提起python文件,经常会听到3个名词,python脚本,python模块,python包.脚本的概念是从py ...
-
ToString() 格式化字符串
例如i=: i.ToString().PadLeft(,'); 固定长度为10,左不足补0,结果为0000000001:
-
POJ1269+直线相交
求相交点 /* 线段相交模板:判相交.求交点 */ #include<stdio.h> #include<string.h> #include<stdlib.h> ...
-
iptables 配置需要保存
iptables-save > /root/myiptables 将iptables规则导入到文件/root/myiptablse iptables-restore < /root/myi ...
-
noip 2012 疫情控制
/* 考试的时候没想出正解 也没打暴力 时间不够了 随便yy了几种情况按出现的先后顺序处理而没有贪心 的了20分 不粘了 正解是围绕首都的儿子来搞的 显然先二分答案 对于每个限定的最大时间 我们尝试着 ...
-
[Jquery] 操作html 不常用元素方法大全
除http://www.w3school.com.cn/jquery/jquery_selectors.asp上的以外该大全应都有. 第一章 input控件篇 1.操作select 下拉框 1.1 获 ...
-
Light OJ 1104 Birthday Pardo(生日悖论)
ime Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Description Sometime ...
-
【.Net Framework 体积大?】不安装.net framework 也能运行!?原理简介-2
接上一篇 [.Net Framework 体积大?]不安装.net framework 也能运行!?开篇叙述-1 昨天写了一个引子,还是有读者对这套“小把戏”感兴趣.那么不辜负大家的希望,争取博主不做 ...