@[DengDuck](/user/501947) 要莫比乌斯吧，这个不加容斥会重
by Caiest_Oier @ 2023-04-20 17:39:54
@[Caiest_Oier](/user/932169) 会吗？可是我的结果是比答案小很多。
by DengDuck @ 2023-04-20 17:40:49
@[DengDuck](/user/501947) 你是相减自然就大小不定了
by Caiest_Oier @ 2023-04-20 17:41:21
相减两边多出来的不一样
by Caiest_Oier @ 2023-04-20 17:41:42
为啥是 $\lfloor n/i\rfloor-1$ 啊。
$$\varphi(n)=\sum_{i=1}^n[i\perp n]$$
$$n-\varphi(n)=\sum_{i=1}^n[\gcd\{i,n\}>1]$$
你这个怎么反推一个 $i$ 对哪些 $n$ 贡献的。。。
by myee @ 2023-04-20 17:42:43
@[DengDuck](/user/501947) 很显然吗，我对数论不熟，没看出来。不过这个思路如果对的话，phi 的前缀和岂不是能做到 $\sqrt n$ 甚至 $n^{1/3} \log n$ 了？
by NaCly_Fish @ 2023-04-20 17:42:45
@[Caiest_Oier](/user/932169) 我直觉上不会重吧，求个Hack
by DengDuck @ 2023-04-20 17:42:55
> 不然这就是一个典型的莫比乌斯反演问题，或者杜教筛之类的，但是时间复杂度无法通过这题
莫反并没有复杂度，莫反指的是 $\mu\times1=\epsilon$ 这一步
杜教筛复杂度 $\mathcal{O}(n^{2/3})$，对于 $10^{12}$ 不一定完全无法通过（？）
另外欧拉函数是 \varphi 不是 \phi
****
问题所在是 $i\nmid j\to \gcd(i,j)=1$ 这一步不成立，如 $(4,6)$。贡献不能这么算。
by fjy666 @ 2023-04-20 17:43:55
@[myee](/user/105050) $i$对它的倍数有贡献啊
by DengDuck @ 2023-04-20 17:44:05
@[DengDuck](/user/501947) 显然不仅对倍数有贡献吧。。。
by myee @ 2023-04-20 17:44:33