http://www.elijahqi.win/archives/3444
Description

设d(x)为x的约数个数,给定N、M,求

Input

输入文件包含多组测试数据。

第一行,一个整数T,表示测试数据的组数。
接下来的T行,每行两个整数N、M。

Output

T行,每行一个整数,表示你所求的答案。

Sample Input

2
7 4
5 6
Sample Output

110
121
HINT

1<=N, M<=50000

1<=T<=50000
Source

Round 1 感谢yts1999上传
考虑先化简原公式

i=1nj=1mσ(ij)


i=1nj=1mx|iy|j[gcd(x,y)==1]


x=1ny=1mx|iy|j[gcd(x,y)==1]


x=1ny=1mx|iy|jd|gcd(x,y)μ(d)


x=1ny=1mnxmyd|gcd(x,y)μ(d)


d=1nμ(d)d|xd|ynxmy


d=1nμ(d)x=1ni=1xdni×dy=1mi=1ydmi×d


那么我们只要

n(n)

的预处理我后面那块内容即可

f[x]=i=1xxi


然后预处理莫比乌斯的前缀和即可在sqrt的时间内解决这题

 

 

分类: 莫比乌斯

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论