博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj2301(莫比乌斯反演)
阅读量:5774 次
发布时间:2019-06-18

本文共 1663 字,大约阅读时间需要 5 分钟。

题意

求区间 [a, b] 和 区间 [c, d] 有多少对数 (x, y) 使得 gcd(x, y) = k 。

分析

考虑用容斥分成四次查询,
对于每次查询区间 [1, n] [1, m] 有多少对数使得 gcd = k ,等价于 [1, m / k] [1, n / k] 使得 gcd = 1。
考虑函数 F(k) = (n / k) * (m / k) 表示区间 [1, n] [1, m] 使得 gcd(x, y) 为 k 的倍数的个数。
函数 f(k) 表示区间 [1, n] [1, m] 使得 gcd(x, y) 为 k 的个数。
$ F(d) = \sum_{k\mid d}f(k) => f(k) = \sum_{k\mid d}\mu(\frac d k)F(d) $
f(1) 即为答案。

算法还需要优化,考虑 n / k 这个函数,当 k 越大变化越趋于平缓,也就是说一个整数值会对应一个连续的 k 值区间,对于这些相同的值可以预处理 \(\mu\) 函数前缀和,对于 n 和 m 存在公共连续区间的部分 F 函数值不变,直接全部加上即可。

code

#include
using namespace std;typedef long long ll;const int MAXN = 1e6 + 10;int not_prime[MAXN];int prime[MAXN];int mu[MAXN];void getMu() { mu[1] = 1; int cnt = 0; for(int i = 2; i < MAXN; i++) { if(!not_prime[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j = 0; i * prime[j] < MAXN; j++) { not_prime[i * prime[j]] = 1; if(i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } mu[i * prime[j]] = -mu[i]; } } for(int i = 1; i < MAXN; i++) mu[i] += mu[i - 1]; // 前缀和}ll cal(int m, int n, int k) { int last; m /= k; n /= k; ll s = 0; for(int i = 1; i <= min(n, m); i = last + 1) { last = min(n / (n / i), m / (m / i)); s += (ll)(mu[last] - mu[i - 1]) * (m / i) * (n / i); } return s;}int main() { getMu(); 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("%d\n", cal(b, d, k) - cal(a - 1, d, k) - cal(b, c - 1, k) + cal(a - 1, c - 1, k)); } return 0;}

转载于:https://www.cnblogs.com/ftae/p/6995450.html

你可能感兴趣的文章
【BZOJ】3524: [Poi2014]Couriers
查看>>
Qt源码编译
查看>>
A3: pythagorean
查看>>
长沙理工大学第十二届ACM大赛-重现赛
查看>>
深入浅析java web log4j 配置及在web项目中配置Log4j的技巧
查看>>
SQL语句复习
查看>>
修改tomcat默认端口号8080
查看>>
Extra Credits: Free Speech 06,07
查看>>
移动端如何用swiper实现导航栏效果
查看>>
80端口被System进程占用问题
查看>>
sys.argv的意义及用法
查看>>
Linux命令大全
查看>>
Python 时间使用
查看>>
最优化问题
查看>>
Learning to Rank 之 listwise ranking
查看>>
数列分块入门 9 / 蒲公英
查看>>
java常用正则表达式
查看>>
java中父类构造方法中的this指向谁
查看>>
修炼Python基础篇-字典(Dictionary)学习
查看>>
Go语言简介
查看>>