首页 > 其他分享 >题解 P9489【ZHY 的表示法】

题解 P9489【ZHY 的表示法】

时间:2023-08-01 22:11:49浏览次数:48  
标签:P9489 ZHY 题解 rfloor 答案 max

容易想到将所求差分,变为 \([1,r]\) 的答案减去 \([1,l-1]\) 的答案。

直觉告诉我们所谓的“实数 \(y\)”就是没事闲的,其实只需要整数就可以。然后这种酷似整除分块的结构提示我们很多 \(y\) 的取值都是多余的,只需要保留所有是 \(x_i\) 的倍数的取值就做到了不重不漏。

要求 \([1,k]\) 的答案,我们可以先二分出最大的满足 \(\sum\lfloor\frac{y}{x_i}\rfloor\le k\) 的 \(y_{\max}\),然后不超过 \(y_{\max}\) 的是 \(x_i\) 的倍数的数的个数即为答案。

这是一个经典容斥,记 \(X\) 为所有 \(x_i\) 构成的集合,答案即为:

\[\sum\limits_{S\subseteq X}(-1)^{|S|-1}\left\lfloor\frac{y_{\max}}{\operatorname{lcm}S}\right\rfloor \]

需要注意的是 \(\operatorname{lcm}S\) 可能特别巨大,在计算过程中超过 \(y_{\max}\) 了就可以退出了。

容斥复杂度好像写高了,不过也过了,防 hack 就不放代码了。

标签:P9489,ZHY,题解,rfloor,答案,max
From: https://www.cnblogs.com/ruierqwq/p/LG-P9489.html

相关文章

  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现,Vika以及她的朋友都不能走对角线,在这种情况下Vika和朋友的距离为偶数,且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心,枚举颜色,找到相邻距离最大的两块木板,记该距离为\(......
  • ARC089B 题解
    problem&blog。给一个比较暴躁的做法。若要求\((x,y)\)的颜色为White,等价于要求\((x+k,y)\)的颜色为Black;要求\((x,y)\)的颜色为Black,等价于要求\((x\bmod2k,y\bmod2k)\)为Black。于是将全部点以黑点的形式塞到左上角\(2k\times2k\)矩阵里。枚举黑白的「分......
  • Codeforces Round 887 (Div. 2) 题解
    A.Desorting题目的核心操作就是选定一个位置\(i\),使得:对于所有\(j\lei\),\(a_j\leftarrowa_j+1\)对于所有\(j>i\),\(a_j\leftarrowa_j-1\)这样一来,操作后\(a_{i+1}-a_i\)的值就会\(-2\)因为\(a_{i+1}-a_i<0\)时,也意味着\(a_i>a_{i+1}\),所以就达到了要求那么题......
  • RTSP流媒体服务器LntonNVR(源码版)平台硬件设备拔电关闭后不能自动重启的问题解决方案
    LntonNVR视频边缘计算网关可以放置在项目现场,7x24小时不间断使用,通电联网即可成功运行,部署操作十分简单。我们在测试时,将LntonNVR注册到服务启动,拔掉硬件设备的电源后,再次恢复供电,发现LntonNVR服务并没有再次启动。对此我们也进行了分析与排查。排查步骤如下:1、首先检查是否已经......
  • 【题解】Luogu[P2420] 让我们异或吧
    Link看到是树,又多组询问,立马想到类似的求和问题,异或不好理解,我们想求和怎么做,维护\(dis_i\)表示\(i\)节点到根的权值和,那么对于\(u,v\)两点路径上的权值和就是\(dis_u+dis_v-2\timesdis_{\mathrm{lca}(u,v)}\),这是很经典的问题了。事实上刚才的求和我们可以转化一下,我们......
  • 国标GB28181视频平台LntonGBS(源码版)国标平台出现报错“缺失dll文件”的问题解决方案
    LntonGBS是基于国标GB28181协议的视频云服务平台,它可以支持国标协议的设备接入,在视频能力上能实现直播、录像存储、检索与回放、云台控制、告警上报、语音对讲、平台级联等功能,既能作为业务平台使用,也能作为能力层平台调用。技术人员在用户服务器部署LntonGBS平台,提示缺失某个dll文......
  • P2216 理想的正方形 题解
    P2216理想的正方形(为什么要写这篇题解?因为我β搞的心态炸了)食用此题解所需:有基础的双端队列知识与一只可爱的\(C++\)传送门:起飞!1.思考嗯,一看数据范围,\(a,b\leq1,000\),就知道这道题一定是一道\(\operatorname{O}(ab)\)的题(因为输入就已经达到\(100,000\)级别了,就算......
  • 国标GB28181视频平台LntonGBS(源码版)国标视频平台大屏播放时出现数据未推送的问题解决
    LntonGBS平台实现视频直播、转码与分发、平台级联、云台控制等,拥有灵活丰富的视频能力。平台基于云边端一体化架构,在很多场景中均有落地项目应用,如智慧工地、智慧安防、智慧工厂、智慧园区等。近期有用户反馈其定制版LntonGBS平台现场播放24路上大屏时有部分通道存在30秒左右出现未......
  • P9481 [NOI2023] 贸易 题解
    题目链接题目要求我们求出任意两点间最短路径之和,由于图比较特殊,除树边外只有祖先到其子树内的边,我们首先考虑最短路径有没有什么特殊性质。注意到两点之间的最短路分为一下三种:节点到其祖先的最短路:直接沿着树边向上走即可,否则一定会走多余的边,不是最优。节点到其子树的......
  • 题解 [NOI2020] 命运
    Link题意给定一棵\(n\)个节点的有根树和\(m\)条祖先到后代的链。问有多少种把边权设置为\(0\)或\(1\)的方案使得每条链上至少有一条边是\(1\)。答案对\(998244353\)取模。\(1\leqn,m\leq5\times10^5\)题解我们将链的下端称为限制的起点。容易发现,对于同一......