[bzoj2301][HAOI2011]Problem B —— 莫比乌斯反演+容斥原理

时间:2022-09-23 00:13:09

题意

给定a, b, c, d, k,求出:

\[\sum_{i=a}^b\sum_{j=c}^d[gcd(i, j) = k]
\]

题解

为方便表述,我们设

\[calc(\alpha, \beta) = \sum_{i=1}^{\alpha}\sum_{j=1}^{\beta}[gcd(i, j) = k]
\]

令\(A = \{ (x, y) | x < a\}\), \(B = \{(x, y)|y < c\}\),

根据容斥原理,

\[|S| = |U| - |A| - |B| + |A \cap B|
\]

所以,原式就是:

\[calc(b, d) - calc(a-1 ,d) - calc(b, c-1) + calc(a-1, c-1)
\]

这样我们就把一个询问拆分成了四个询问,即,问题就转换成了计算\(calc(\alpha, \beta)\)

\[f(x) = \sum_{i=1}^b\sum_{j=1}^d[gcd(i, j) = x]
\]

显然,f(x)并不方便计算,但是如果我们设

\[F(x) = \sum_{i=1}^b\sum_{j=1}^d[gcd(i, j) = \lambda, x|\lambda]
\]

我们可以得出F(x)与f(x)的关系,

\[F(x) = \sum_{x|d} f(d)
\]

F(x)就相对好计算的多,我们很容易有:

\[F(x) =\lfloor \frac{b}{i}\rfloor \lfloor\frac{d}{i} \rfloor
\]

但是这一点对于我这种蒟蒻来说并不显然,所以这里给出一个证明。

同样地,令\(\lambda = gcd(i, j)\),如果\(x|\lambda\),那么我们可以得出:

1.\(x|i\)

2.\(x|j\)

反过来证明必要性:

如果\(x|i \&\& x|j\),那么x一定是i和j的公约数,所以一定有

\(x \leq \lambda\)

又因为x和\(\lambda\)都是公约数,所以\(x|\lambda\),所以必要性得证。

所以x是i和j的公约数是数对(i, j)可以对F(x)的充分必要条件。

我们使用分步原理,首先在[1,n]中寻找x的倍数个数,然后在[1,m]里找,乘起来就可以了。

然后,根据mobius反演(《具体数学》P113 4.9 \(\phi\)函数与\(\mu\)函数)

\[f(x) =\sum_{d|x} \mu(d) F(\frac{x}{d})
\]

但是这种反演形式并不适合解此题,我们采取另外一种形式:

\[f(x) = \sum_{x|d} \mu(\frac{d}{x}) F(d) = \sum_{x|d}\mu(\frac{d}{x}) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor
\]

由于枚举倍数显然只需要枚举到min(n, m),所以复杂度为\(\Theta(n+m)\)

根据神犇的课件

观察式子,我们发现:

\(\lfloor \frac{n}{d} \rfloor\)的取值最多有\(2 \sqrt n\)种(约数的个数),所以如果我们枚举\(\lfloor \frac{n/m}{d} \rfloor\)的取值,只需要枚举\(2(\sqrt n + \sqrt m)\)即可,复杂度就成了\(\Theta (\sqrt n + \sqrt m)\)

对于同一个取值,\(\mu\)函数是不同的,但是属于一个区间,我们可以统一求和,维护一个前缀和即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int T, a, b, c, d, k;
int mu[maxn+5], sumu[maxn+5], prime[maxn+5], check[maxn+5];
int tot = 0;
void get_mu() {
memset(check, 0, sizeof(check));
mu[1] = 1;
for(int i = 2; i <= maxn; i++) {
if(!check[i]) {
prime[tot++] = i;
mu[i] = -1;
}
for(int j = 0; j < tot; j++) {
if(i * prime[j] > maxn) break;
check[i * prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}
} void init() {
get_mu();
for(int i = 1; i <= maxn; i++) sumu[i] = sumu[i-1] + mu[i];
} int calc(int n, int m) {
n/=k;
m/=k;
int ret = 0;
int last;
if(n > m) swap(n, m);
for(int i = 1; i <= n; i = last + 1) {
last = min(n / (n/i), m / (m/i));
ret += (n / i) * (m / i) * (sumu[last] - sumu[i-1]);
}
return ret;
}
int main() {
init();
scanf("%d", &T);
while(T--) {
scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
int ans = calc(b, d) - calc(a-1, d) - calc(b, c-1) + calc(a-1, c-1);
printf("%d\n", ans);
}
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. 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 第一行一个整数 ...

  4. &lbrack;HAOI2011&rsqb;&lbrack;bzoj2301&rsqb; Problem b &lbrack;莫比乌斯反演&plus;容斥原理&plus;分块前缀和优化&rsqb;

    题面: 传送门 有洛谷就尽量放洛谷链接呗,界面友好一点 思路: 和HDU1695比较像,但是这一回有50000组数据,直接莫比乌斯反演慢慢加的话会T 先解决一个前置问题:怎么处理a,c不是1的情况? ...

  5. &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, ...

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

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

  7. 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, ...

  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\) 首先 ...

随机推荐

  1. knockout应用开发指南(完整版)

    http://www.cnblogs.com/TomXu/archive/2011/11/21/2257154.html

  2. StringExtensions

    public static string MakeSafeSql(this string s) { string t = s; t = t.Replace("'", "' ...

  3. 模拟赛1030d1

    [问题描述]从1− ?中找一些数乘起来使得答案是一个完全平方数,求这个完全平方数最大可能是多少.[输入格式]第一行一个数字?.[输出格式]一行一个整数代表答案对100000007取模之后的答案.[样例 ...

  4. python 把数据 json格式输出

    有个要求需要在python的标准输出时候显示json格式数据,如果缩进显示查看数据效果会很好,这里使用json的包会有很多操作 import json date = {u'versions': [{u ...

  5. SDC&lpar;7&rpar; -- 关于使能信号的时序放松

    先看下图: 假如使能信号的有效时间为时钟周期的2倍,此时需要使用 set_multicycle_path 放松使能信号 sel_xy_nab ,若是每个寄存器使能端都约束一遍,那就太麻烦了: 这时可以 ...

  6. BZOJ&lowbar;1011&lowbar;&lbrack;HNOI2008&rsqb;&lowbar;遥远的行星&lowbar;&lpar;近似&rpar;

    描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1011 \(n\)个行星,第\(i\)颗行星的质量为\(m_i\),给出一个很小的常数\(A\) ...

  7. Scientific Toolworks Understand for linux安装方法

    1.首先从官网http://www.scitools.com/download/index.php下载Linux版本 2.解压到安装目录下: 32位:gzip -cd Understand-3.1.6 ...

  8. DEDECMS中的几个常见的自定义常量DEDEMEMBER等位置

    http://www.dede58.com/a/dedejq/3567.html dedecms新建栏目时默认都是允许投稿的,可以投稿本来对网站来说是件好事,但是dedecms是开源的,使用太广泛了, ...

  9. ionic3开发环境的搭建 记录!

    总的来说都很顺利,毕竟已经打包成功在手机上面跑起来了,给的两个教程很给力,基本没有误差,照着步骤敲没问题,打包命令有所更新目前已修正,吃一堑长一智下面说下其中遇到的问题:1.第一点是ionic ser ...

  10. SQL SERVER 2008 误删数据且无全备恢复方法

    原文:http://www.jb51.net/article/84932.htm SQL Server中误删除数据的恢复本来不是件难事,从事务日志恢复即可.但是,这个恢复需要有两个前提条件: 1. 至 ...