\\根据莫比乌斯反演，可以把式子化为\因为$d|gcd(x,y) $ => \所以式子变为 \. 用n/d的取值分一个段，然后对mu求一个前缀和即可解决……
t<=1e4个询问每次问n,m<=1e7，$\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m}lcm(x,y)$。首先题目要求的是$\sum_{1\leqslant x\leqslant
一般来讲是求与gcd有关的。那么可以反演得到模型：。简单粗暴可以暴力去除，最坏复杂度是O. 当需要求情况三的时候，K数组里就是y，求i1可以再维护一个数组G[x]=P[x]K[x]，只需要G初始设为1，在K[x]++的时候G[x]*=p就可以了。O求出i1
安科网(Ancii)，中国第一极客网
Copyright © 2013 - 2019 Ancii.com
京ICP备18063983号-5 京公网安备11010802014868号