ZHY
P9489 ZHY 的表示法
原题 没做过容斥题,因此即使是绿题也很难想 首先看数据范围 \(n \leq 25\) 可以想到这题复杂度应该是指数级别的 我们先对答案差分,\(ans = solve(r) - solve(l-1)\),因此我们只需要计算\(solve(x)\)即可 可以表示出的取值一定能被某个 \(x_i\) ......
P9488 ZHY 的生成树
`2023-07-31 19:29:29 solution` [P9488 ZHY 的生成树](https://www.luogu.com.cn/problem/P9488) ## 前言 这道题就非常的巧,下午上午上课刚讲完筛法,下午就考到了一个很像筛法的题。当时看到这个数据范围尽往线性做法想了,后 ......
题解 P9489【ZHY 的表示法】
容易想到将所求差分,变为 $[1,r]$ 的答案减去 $[1,l-1]$ 的答案。 直觉告诉我们所谓的“实数 $y$”就是没事闲的,其实只需要整数就可以。然后这种酷似整除分块的结构提示我们很多 $y$ 的取值都是多余的,只需要保留所有是 $x_i$ 的倍数的取值就做到了不重不漏。 要求 $[1,k] ......