在颓废了一天之后决定写一个题解.因为我觉得这题挺有意思.
我们需要转化一下式子.把原来的a,b改成A,B.设d=gcd(A,B),A=ad,B=bd.
那么(a+b)d | abd2,即(a+b)|ab*d.
又因为gcd(a,b)=1,所以(a+b)一定与a,b都互质.于是(a+b)|d.
设t*(a+b)=d.那么因为bd≤n,所以t(a+b)*b≤n.那么b是sqrt(n)级别的.且我们只需要统计三元组(a,b,t)的个数就行了.
answer=∑b∑a(n/b)/(a+b)(gcd(a,b)=1)然后这个玩意看上去好像是个长得怪异一点的狄利克雷卷积啊.
于是就是要求[l, r]中与b互质的数的个数?这个玩意等于∑i|bu(i)*(r/i).然后发现可以把b分解质因数.而且只留下u不为0的.于是就能出奇迹辣好厉害ovo