某些莫反题的其他线性复杂度做法？
  • 板块学术版
  • 楼主AffineRing
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/10/27 22:11
  • 上次更新2023/11/5 09:42:33
查看原帖
某些莫反题的其他线性复杂度做法？
399250
AffineRing楼主2020/10/27 22:11

比如有这么一题：

给定整数NN，求 1≤x,y≤N1 \leq x,y \leq N 且gcd⁡(x,y)\gcd(x,y) 为素数的数对 (x,y)(x,y) 有多少对.

根据套路，此题为

∑p∑i=1N/p∑j=1N/p[gcd(i,j)=1]\sum\limits_p\sum\limits_{i=1}^{N/p}\sum\limits_{j=1}^{N/p}[gcd(i,j)=1]

到这里都差不多，但是按照套路应该是直接开始反演。但是发现题目就是统计互质数对个数。

所以就变成了

∑p(2×∑i=1N/pφ(i)−1)\sum\limits_p\left(2\times\sum\limits_{i=1}^{N/p}\varphi(i)-1\right)

然后线筛欧拉函数，然后求前缀和，然后枚举素数，然后似乎可以O(n)O(n)完成此题？

所以这和直接反演哪个好啊，哪个通用

2020/10/27 22:11