题目要求用数学一点的形式表达出来就是统计有多少a,b满足
1.\(1\leq a\leq n ,1\leq b\leq m\)
2.\(\exists k \in N^* ,使得b \times gcd(a,b)=k\times (a+ b)\)
首先,把a和b改写,使得\(gcd(a,b)\)消失
\(a=q*d,b=p*d\),则,\(gcd(a,b)=d\)
条件二变为:\(p\times d^2= k\times (q\times d +q\times d)\)
转化为判断,是否存在正整数\(k\),使得\(p\times d= k\times (q +p)\)成立,也就是\(\frac {p\times d} {q+p}= k\)
也就是我们要对每个\(gcd(q,p)=1\)的数对,验证是否存在这样的\(q\times d\),使得\(\frac {p\times d} {q+p}\)为一个整数。
呃,应该说是对每个\(gcd(q,p)=1\)的数对,统计有多少这样的\(q\times d\),使得\(\frac {p\times d} {q+p}\)为一个整数。
但是这还是不好统计。但是有一个很明显的地方,\(gcd(q,p)=1\),那么,\(gcd(q+p,p)\)等于多少呢?
等于1。辗转相除法可以证明。
所以我们需要统计的其实不是\(q\times d\),而是\(d\)。
统计这个的个数,其实就是枚举所有\(gcd(q,p)=1\)的数对,然后用一个算式直接统计对应的d有多少个。这样的统计是不重复的。
枚举所有的q,p看似不可能,是\(O(nm)\)的,但是从上面的式子中,我们可以发现,我们要找的是\(\frac {d} {q+p}\),$pd\leq n \(,而刚刚的式子表示,\)d\geq q+p\(,我们这里取极端的情况,\)p=1\(,则要求变为\)d>q$ ,结合上面的,$pd\leq n \(可以得到,\)q^2\leq n$,对p也是同理。
所以我们只需要枚举所有\(1\leq q \leq \sqrt n,和1\leq p \leq \sqrt m\),然后统计的部分可以用算式,也可以用循环,用循环的复杂度总体就是\(O({nm}^{\frac{1}{2}}\times ln (nm))\),可以通过