枚举gcd+启发式合并：GYM102832K
枚举gcd+启发式合并：GYM102832K
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133807724
https://codeforces.com/gym/102832/problem/K
首先从值域上预处理，对数不会很多。
场上想的是建树然后启发式合并。
但发现合并这个过程直接用类似并查集的启发式合并即可
预处理方面先枚举gcd， 再枚举x可以做到两个log
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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
质因子拆贡献+朴素容斥：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-07-04
初等数论入门 Lesson 1 整除体系与贝祖理论
初等数论入门 Lesson 1 整除 b∣ab \mid ab∣a 等价于 a=bqa = bqa=bq 等价于 a mod b=0a\bmod b = 0amodb=0，读作 bbb 整除 aaa。 除法算式定理 定理：设 a,b∈Z, b>0a,b \in \mathbb{Z},\ b>0a,b∈Z, b>0，则存在唯一的整数对 (q,r)(q,r)(q,r)，满足： a=bq+r,0≤r<ba = bq + r,\quad 0 \le r < b a=bq+r,0≤r<b gcd-lcm 关系 gcd(a,b)⋅lcm(a,b)=∣ab∣\g...