1. 题目

传送门= ̄ω ̄=

2. 题解

wcnmlgb刚刚写到一半不知道按到什么键了回退到上一页,写的全没了wcnmlgb

个人觉得出题人就是个sb,既然区间左端都是1,干嘛还要输入?

设$f(d)$为$gcd(x,y)==d$的数对个数,$g(d)$为$gcd(x,y)\% d==0$的数对个数。

这两个函数有什么关系呢?

函数$g(d)$只要满足$gcd(x,y)$是d的倍数就行了,而$f(d)$要满足$gcd(x,y)==d$,所以其实g包含了f。

具体是怎样的关系呢?

$g(d)=f(d\times 1)+f(d\times 2)+f(d\times 3)+...$

在本题中,正式且装逼地说,就是这个:

$g(n)=\sum\limits_{n|d}{f(d)}(d<=min(a,b))$

是不是很眼熟?我才不会告诉你我是从boshi dalao的博客里复制出来的╭(╯^╰)╮

这不就是莫比乌斯反演吗?虽然n和d掉了个个儿,那还不是老套路,反演的时候也掉个个儿就行了。

所以我们通过莫比乌斯反演公式可以得到:

$f(n)=\sum\limits_{n|d}{u(\frac{d}{n})g(d)}(d<=min(a,b))$

我们要求的就是$f(k)$。

原问题是$gcd(x,y)==k,x\in [1,a],y\in[1,b]$,我们为了方便计算,不妨把整个式子都除以k,就得到了:

$gcd(x,y)==1,x\in [1,a/k],y\in[1,b/k]$

这样我们要求的就是$f(1)$了,这样不需要判断n是否能整除d。即:

$f(1)=\sum\ {u(d)g(d)}(d<=min(a,b))$

莫比乌斯函数u的值可以用线性筛求得,那函数g呢?

其实很简单。

$gcd(x,y)\% d==0$,那么x,y一定都是d的倍数。在区间[1,lim]中是d的倍数的数的个数是floor(lim/d),那么x的值有floor(a/d)种取法,y的值有floor(b/d)种取法,所以乘法原理得到一共有floor(a/d)×floor(b/d)种取法,所以:

$g(d)=\frac{a}{d}\times \frac{b}{d}$

然后还有,问题中说了,x,y和y,x算一种解法。所以我们统计一下$x,y\in min(a,b)$的个数,最后答案减去这个数就行了。

那么问题就迎刃而解了。

代码: