题意
给定a, b, c, d, k,求出:
\]
题解
为方便表述,我们设
\]
令\(A = \{ (x, y) | x < a\}\), \(B = \{(x, y)|y < c\}\),
根据容斥原理,
\]
所以,原式就是:
\]
这样我们就把一个询问拆分成了四个询问,即,问题就转换成了计算\(calc(\alpha, \beta)\)
令
\]
显然,f(x)并不方便计算,但是如果我们设
\]
我们可以得出F(x)与f(x)的关系,
\]
F(x)就相对好计算的多,我们很容易有:
\]
但是这一点对于我这种蒟蒻来说并不显然,所以这里给出一个证明。
同样地,令\(\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\)函数):
\]
但是这种反演形式并不适合解此题,我们采取另外一种形式:
\]
由于枚举倍数显然只需要枚举到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 —— 莫比乌斯反演+容斥原理的更多相关文章
-
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(莫比乌斯反演,容斥)
Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. Input 第一行一个整数 ...
-
[HAOI2011][bzoj2301] Problem b [莫比乌斯反演+容斥原理+分块前缀和优化]
题面: 传送门 有洛谷就尽量放洛谷链接呗,界面友好一点 思路: 和HDU1695比较像,但是这一回有50000组数据,直接莫比乌斯反演慢慢加的话会T 先解决一个前置问题:怎么处理a,c不是1的情况? ...
-
[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\) 首先 ...
随机推荐
-
knockout应用开发指南(完整版)
http://www.cnblogs.com/TomXu/archive/2011/11/21/2257154.html
-
StringExtensions
public static string MakeSafeSql(this string s) { string t = s; t = t.Replace("'", "' ...
-
模拟赛1030d1
[问题描述]从1− ?中找一些数乘起来使得答案是一个完全平方数,求这个完全平方数最大可能是多少.[输入格式]第一行一个数字?.[输出格式]一行一个整数代表答案对100000007取模之后的答案.[样例 ...
-
python 把数据 json格式输出
有个要求需要在python的标准输出时候显示json格式数据,如果缩进显示查看数据效果会很好,这里使用json的包会有很多操作 import json date = {u'versions': [{u ...
-
SDC(7) -- 关于使能信号的时序放松
先看下图: 假如使能信号的有效时间为时钟周期的2倍,此时需要使用 set_multicycle_path 放松使能信号 sel_xy_nab ,若是每个寄存器使能端都约束一遍,那就太麻烦了: 这时可以 ...
-
BZOJ_1011_[HNOI2008]_遥远的行星_(近似)
描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1011 \(n\)个行星,第\(i\)颗行星的质量为\(m_i\),给出一个很小的常数\(A\) ...
-
Scientific Toolworks Understand for linux安装方法
1.首先从官网http://www.scitools.com/download/index.php下载Linux版本 2.解压到安装目录下: 32位:gzip -cd Understand-3.1.6 ...
-
DEDECMS中的几个常见的自定义常量DEDEMEMBER等位置
http://www.dede58.com/a/dedejq/3567.html dedecms新建栏目时默认都是允许投稿的,可以投稿本来对网站来说是件好事,但是dedecms是开源的,使用太广泛了, ...
-
ionic3开发环境的搭建 记录!
总的来说都很顺利,毕竟已经打包成功在手机上面跑起来了,给的两个教程很给力,基本没有误差,照着步骤敲没问题,打包命令有所更新目前已修正,吃一堑长一智下面说下其中遇到的问题:1.第一点是ionic ser ...
-
SQL SERVER 2008 误删数据且无全备恢复方法
原文:http://www.jb51.net/article/84932.htm SQL Server中误删除数据的恢复本来不是件难事,从事务日志恢复即可.但是,这个恢复需要有两个前提条件: 1. 至 ...