题目是求:
∑i=1n∑j=1mmin(⌊in⌋,⌊jm⌋)×[gcd(i,j)=1]
有一个结论就是这个柿子的结果是 n×m,但是自己想了一种 O(n) 的做法
大概就是记录 2n+2m 个三元组 L,R,V,一个是 n 的整除分块的每一部分,另一个是 m 的。
然后在这上面双指针可以做到整除分块套整除分块,但是因为其中一个的上界是 n 所以只能做到 O(n×n)=O(n)。
有没有更快的做法啊/yiw 至于为啥要用这个做法,我只要把 min 改成 max 就行了,复杂度还变成了 n^{3/4}