BZOJ 2301 [HAOI2011]Problem b (容斥+莫比乌斯反演+分块优化 详解)

本文主要是介绍BZOJ 2301 [HAOI2011]Problem b (容斥+莫比乌斯反演+分块优化 详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 2096  Solved: 909
[Submit][Status][Discuss]

Description

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

Input

第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k

Output

共n行,每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2301


题目分析:首先n就是五万,因此每次即使是O(n)的计算总的下来也是O(n^2)了,因此对于每次操作我们要让时间复杂度小于O(n),题意很清楚

先将原式变形:

a / k <= x / k <= b / k,c / k <= y / k <= d / k,gcd(x / k, y / k) = 1,令cal(b / k,d / k)为1 <= x / k <= b / k,1 <= y / k <= d / k时取出的满足条件的个数,则根据容斥原理有

ans = cal(b / k,d / k) - cal((a - 1) / k,d / k) - cal((c - 1) / k,b / k) + cal((a - 1) / k,(c - 1) / k),因为1~a-1和1~c-1都不在我们所求的范围内,又减的时候这段区间减了两次,因此要再加上一个,接下来看cal函数,这里要用到分块求和,如果不做优化,就是直接枚举公约数ans += mob[i] * (l / i) * (r / i)但这样会超时,考虑到不能整除的特性,在很大一段区间内(l / i)和(r / i)的值是相同的,举个简单的例子,l = 10,r  =  11那么可以看出 i从6到10,l / i和r / i的值都是1,因此考虑分块求和,从i开始最长的相等区间长度为min(l / (l / i),r / (r / i)),这里如果不能理解的话,比如l / (l / i),设l / i = p,p表示整除时的值,那么l / p就是从i开始整除值为p的个数了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 50005;
int p[MAX], mob[MAX], sum[MAX];
bool prime[MAX];
int a, b, c, d, k;void Mobius()
{int pnum = 0;memset(prime, true, sizeof(prime));memset(sum, 0, sizeof(sum));mob[1] = 1;sum[1] = 1;for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}sum[i] = sum[i - 1] + mob[i];}
}int cal(int l, int r)
{if(l > r)swap(l, r);int ans = 0;for(int i = 1, last = 0; i <= l; i = last + 1){last = min(l / (l / i), r / (r / i));ans += (l / i) * (r / i) * (sum[last] - sum[i - 1]);}return ans;
}int main()
{Mobius();int n;scanf("%d", &n);while(n --){scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);int ans = 0;ans += cal(b / k, d / k);ans -= cal((a - 1) / k, d / k);ans -= cal((c - 1) / k, b / k);ans += cal((a - 1) / k, (c - 1) / k);printf("%d\n", ans);   }
}


这篇关于BZOJ 2301 [HAOI2011]Problem b (容斥+莫比乌斯反演+分块优化 详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829674

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2