用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)∣...
2026-07-04
初等数论入门 Lesson 4 莫比乌斯反演
初等数论入门 Lesson 4 莫比乌斯反演 线性筛求 μ(1…n) μ(1)=1\mu(1)=1μ(1)=1 若 iii 是素数：μ(i)=−1\mu(i)=-1μ(i)=−1 若 imod pj=0i\mod p_j=0imodpj=0，即 pj2∣ip_j^2\mid ipj2∣i，则 μ(i⋅pj)=0\mu(i\cdot p_j)=0μ(i⋅pj)=0 否则：μ(i⋅pj)=−μ(i)\mu(i\cdot p_j)=-\mu(i)μ(i⋅pj)=−μ(i) 基础函数与Dirichlet卷积 单位函数（卷积单位元） ε(n)={1,n=10,n>1\va...
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-10
期望+拆贡献+充斥：CF1349D
期望+拆贡献+充斥：CF1349D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187 第一步：找性质 每个人的期望步数只与总数量 mmm ，总人数 nnn ，自己数量 aia_iai 有关 第二步：转化（难点） 拆贡献：拆成每个人win的期望步数，然后求 ∑E(i)\sum E(i)∑E(i) 容斥：肯定不能直接算。于是考虑算直到第 iii 个人拿完才结束的的期望步数 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， ...
2023-11-06
排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B]
排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B] 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134243178 https://vjudge.net/contest/591700#problem/G 看到排列，先考虑置换换，题意转化为置换环相邻的不能再最终序列上相邻 而这个过程看起来很容斥，所以我们容斥：至少要 xxx 个相邻 我们发现每个置换环的所有边不能全部同时被选，所以我们每个置换环要分开考虑，最后再乘起来 然而这样的复杂度...
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...