用min-max容斥实现lcm与gcd互换
用min-max容斥实现lcm与gcd互换
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698576
lcm本质是每个质因子质数取max，gcd是每个质因子质数取min
然后我们就可以直接套min-max容斥：
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-09
min-max容斥
min-max容斥 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698526 设 S,TS,TS,T 都是可重序列 maxS=∑S⊊TminT(−1)∣T∣−1maxS=\sum_{S\subsetneq T}minT(-1)^{|T|-1}maxS=∑S⊊TminT(−1)∣T∣−1 minS=∑S⊊TmaxT(−1)∣T∣=1minS=\sum_{S\subsetneq T}maxT(-1)^{|T|=1}minS=∑S⊊TmaxT(−1)∣...
2023-09-18
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132978606 首先看到不能走出边界，发现是个反射容斥 对于此题，我们可以采用循环卷积来实现反射容斥 也就是说，如果我们走出了边界，相当于就是走到了另一边 而实现这个过程我们可以把卷完后 i+pi+pi+p 的部分直接平移到 iii 就行 加速这个过程可以用多项式快速幂 1234567891011121314151617181920212223...
2023-10-24
组合计数+容斥：1024T2
组合计数+容斥：1024T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134013962 http://cplusoj.com/d/senior/p/SS231024B?tid=653748c7611b23c4594b05ab 要么是环，要么是链，都可以有两个方向 链的话可以缩成点一起统计 长为2的链如果成二元环不应该乘2，那么考虑容斥 g(i)g(i)g(i) 表示至少有 iii 个二元环不被算错的方案数， ∑i=0kg(i)(−1)k−i\sum...
2023-10-09
质因子拆贡献+朴素容斥：1007T3
质因子拆贡献+朴素容斥：1007T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133697910 http://cplusoj.com/d/senior/p/SS231007C 考虑枚举gcd，然后容斥，恰好转至少。 ggg 表示gcd恰好为 ddd ， fff 表示至少为 ddd 显然有 f(d)=∑d∣ng(n)f(d)=\sum_{d|n}g(n)f(d)=∑d∣ng(n) ，可以直接莫反成： g(d)=∑d∣nf(n)μ(nd)g(d)=\s...
2026-08-02
容斥思想辅助mex计数+CDQ分治：26暑杭电 3-11
容斥思想辅助mex计数+CDQ分治：26暑杭电 3-11 1011 Mex 感觉这道题最巧妙的地方是，用每个位置 iii 去计算对答案的贡献。 也就是钦定0、1、2、3个为位置为mex，然后用容斥计算是否可行 0个位置的贡献为1（即全选） 1个位置的话有 nnn 种，而且显然合法 2个位置，有 (n2)\binom n 2(2n) 种。不合法的情况是形成三维偏序。 3个位置，有 (n3)\binom n 3(3n) 种，不合法的情况是形成二维偏序，根据容斥，要加回三维偏序。 于是总方案为： 1+n+(n2)−∑iABC(i)+(n3)−∑i((AB(i)2)+(AC(i)2)+(B...
2023-10-09
二维反射容斥：P9366
二维反射容斥：P9366 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133707260 https://www.luogu.com.cn/problem/P9366 构造循环矩阵，考虑反射容斥和将军饮马 考虑二维不太好做，我们曼哈顿距离转切比雪夫距离，变成一维的情况。 由于棋盘是正方形的，所以循环长度为 2n+42n+42n+4 。用多项式快速幂预处理，询问记得考虑正负两个方向。 123456789101112131415161718192021222...