用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-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...
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...
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...
2026-07-26
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05 1005 减数游戏 2 博弈 先把博弈论的问题解决掉，怎样是最优的。 目的是让对手尽可能地吃掉有的数 我们来看一个数轴： 只要蓝色是先手： 奇数连续段时，它必然比绿色少吃1个 偶数段时，它和绿色相等 而且通过上面这种策略，它每次都可以占据空白段。 因此，关键在于谁能获得空白段的主动权 而空白段的主动权，只和第一个连续段的长度有关。 如果第一个连续段长度为偶数，那么先手就必胜了。 容斥 不妨令 mex(S)=p\text{mex}(S)=pmex(S)=p，在 1∼p−11\sim p-11∼p−1 内有 rrr 个空，...