bzoj2301 [HAOI2011]Problem b【莫比乌斯反演 分块】

时间:2021-10-01 18:48:21

传送门: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【莫比乌斯反演 分块】的更多相关文章

  1. BZOJ2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lbrack;莫比乌斯反演 容斥原理&rsqb;【学习笔记】

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 4032  Solved: 1817[Submit] ...

  2. BZOJ2301&colon; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 然后对于求这样单个的gcd(x,y)=k的, ...

  3. &lbrack;bzoj2301&rsqb;&lbrack;HAOI2011&rsqb;Problem B —— 莫比乌斯反演&plus;容斥原理

    题意 给定a, b, c, d, k,求出: \[\sum_{i=a}^b\sum_{j=c}^d[gcd(i, j) = k]\] 题解 为方便表述,我们设 \[calc(\alpha, \beta ...

  4. BZOJ2301&colon;&lbrack;HAOI2011&rsqb;Problem b&lpar;莫比乌斯反演&comma;容斥&rpar;

    Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数 ...

  5. Bzoj 2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lpar;莫比乌斯反演&plus;除法分块&rpar;

    2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...

  6. &lbrack;BZOJ1101&amp&semi;BZOJ2301&rsqb;&lbrack;POI2007&rsqb;Zap &lbrack;HAOI2011&rsqb;Problem b&vert;莫比乌斯反演

    对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d. 我们可以令F[n]=使得n|(x,y)的数对(x,y)个数 这个很容易得到,只需要让x, ...

  7. P2522 &lbrack;HAOI2011&rsqb;Problem b &lpar;莫比乌斯反演&rpar;

    题目 P2522 [HAOI2011]Problem b 解析: 具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是,这个题求的是\(\sum_{i=a}^b\sum_{j= ...

  8. BZOJ 2301&colon; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 1007  Solved: 415[Submit][ ...

  9. BZOJ&period;2301&period;&lbrack;HAOI2011&rsqb;Problem B&lpar;莫比乌斯反演 容斥&rpar;

    [Update] 我好像现在都看不懂我当时在写什么了=-= \(Description\) 求\(\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]\) \(Solution\) 首先 ...

  10. &lbrack;POI2007&rsqb;ZAP-Queries &amp&semi;&amp&semi; &lbrack;HAOI2011&rsqb;Problem b 莫比乌斯反演

    1,[POI2007]ZAP-Queries ---题面---题解: 首先列出式子:$$ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i, j) == d]$$ ...

随机推荐

  1. content相关属性

    content属性值 :      width:可视区域的宽度,值可为数字或关键词device-width      height:同width      intial-scale:页面首次被显示是可 ...

  2. java&period;lang&period;Class&period;forName&lpar;String name&comma; boolean initialize&comma; ClassLoader loader&rpar;方法

    描述 Java.lang.Class.forName(String name, boolean initialize, ClassLoader loader) 方法返回与给定字符串名的类或接口的Cla ...

  3. python学习笔记系列----(四)模块

    这一章主要是叙述了python模块的概念以及包的概念,还有它们的使用:收获也是大大的. 提起python文件,经常会听到3个名词,python脚本,python模块,python包.脚本的概念是从py ...

  4. ToString&lpar;&rpar; 格式化字符串

    例如i=: i.ToString().PadLeft(,'); 固定长度为10,左不足补0,结果为0000000001:

  5. POJ1269&plus;直线相交

    求相交点 /* 线段相交模板:判相交.求交点 */ #include<stdio.h> #include<string.h> #include<stdlib.h> ...

  6. iptables 配置需要保存

    iptables-save > /root/myiptables 将iptables规则导入到文件/root/myiptablse iptables-restore < /root/myi ...

  7. noip 2012 疫情控制

    /* 考试的时候没想出正解 也没打暴力 时间不够了 随便yy了几种情况按出现的先后顺序处理而没有贪心 的了20分 不粘了 正解是围绕首都的儿子来搞的 显然先二分答案 对于每个限定的最大时间 我们尝试着 ...

  8. &lbrack;Jquery&rsqb; 操作html 不常用元素方法大全

    除http://www.w3school.com.cn/jquery/jquery_selectors.asp上的以外该大全应都有. 第一章 input控件篇 1.操作select 下拉框 1.1 获 ...

  9. Light OJ 1104 Birthday Pardo&lpar;生日悖论)

    ime Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu   Description Sometime ...

  10. 【&period;Net Framework 体积大?】不安装&period;net framework 也能运行!?原理简介-2

    接上一篇 [.Net Framework 体积大?]不安装.net framework 也能运行!?开篇叙述-1 昨天写了一个引子,还是有读者对这套“小把戏”感兴趣.那么不辜负大家的希望,争取博主不做 ...