Description
给出A，B，考虑所有满足l<=a<=A，l<=b<=B，且不存在n>1使得n^2同时整除a和b的有序数
对(a，b)，求其lcm(a，b)之和。答案模2^30。
Input
第一行一个整数T表示数据组数。接下来T行每行两个整数A，B表示一组数据。
T ≤ 2000,A,B ≤ 4 × 10^6
Output
对每组数据输出一行一个整数表示答案模2^30的值
Sample Input
5
2 2
4 6
3 4
5 1
23333 33333
2 2
4 6
3 4
5 1
23333 33333
Sample Output
7
148
48
15
451085813
148
48
15
451085813
好久没更过博客惹……
这题的话肯定是先式子一波推辣！
$ sum_{i=1}^{A}sum_{j=1}^{B} [gcd(i,j)无平方因子] lcm(i,j) $
$ =sum_{i=1}^{A}sum_{j=1}^{B} μ(gcd(i,j))^2 frac{i*j}{gcd(i,j)} $
$ =sum_{d=1}^{A} μ(d)^2*d sum_{i=1}^{leftlfloorfrac{A}{d}
ight
floor} sum_{j=1}^{leftlfloorfrac{B}{d}
ight
floor} [gcd(i,j)==1] i*j $
$ =sum_{d=1}^{A} μ(d)^2*d sum_{D=1}^{leftlfloorfrac{A}{d}
ight
floor} μ(D)*D^2*f(leftlfloorfrac{A}{d*D}
ight
floor)*f(leftlfloorfrac{B}{d*D}
ight
floor) $
其中$f(x)=frac{x(x+1)}{2}$
（诶，这式子可以看吧……
一开始就推到这里，感觉复杂度$O(n^{frac{2}{3}})$应该差不多，然后就交了两发T……
回来继续推式子吧。
发现与A,B相关的项都只与$d*D$有关，那么试着预处理出每个$d*D$的系数，暴力$Aln(A)$预处理，答案可以$sqrt{A}$的复杂度计算。这样一来所有计算都在预处理上了，交了一发31s卡了过去。
可是这样不优雅！
发现预处理出的系数数组其实是两个积性函数的卷积，那么它也是个积性函数。
打一下表找到质数及其幂位置的规律然后就可以辣，8.6s！
写完感觉这题好良心，用多组数据限制A和B的大小，如果只有单组数据然后A和B很大似乎就得想办法杜教筛或者洲阁筛了呢。
式子都在上边我就不丢代码惹……