Codeforces Round 942 (Div. 2)

题目（Problem - D2. Reverse Card (Hard Version）- Codeforces）：

题面：

给你两个正整数 $n$ ， $m$ 。

请计算满足以下条件的有序数对 $(a, b)$的个数：

• $1\le a\le n$ , $1\le b\le m$ ;
• $b \cdot \gcd(a,b)$ 是 $ a+b $ 的倍数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 10^4$ )。( $1\le t\le 10^4$ ).测试用例说明如下。

每个测试用例的第一行包含两个整数$n$ , $m$ ( $1\le n,m\le 2 \cdot 10^6$)。

保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \cdot 10^6$ 。

输出

为每个测试用例打印一个整数：有效配对的数量。

分析：

$$\begin{aligned} & b*gcd(a,b)=k*(a+b)\\ &不妨设gcd(a,b)=d,则a=p*d,b=q*d\\ &源式化为 (q+p)|qd=k\\ &因为gcd(p,q)=gcd(p+q,q)=1\\ &可得(q+p)|d=k\\ &因为1\le q \le m \& q\le d ,则q \le \sqrt{m} ,同理p \le \sqrt{m}\\ &则可以两层\sqrt{n},\sqrt{m},循环暴力枚举p,q ,用gcd(p,q)作为满足条件\\ &对答案的贡献为ans+=\cfrac {min(\cfrac{n}{p},\cfrac{m}{q})}{(p+q)} 时间复杂度：O(\sqrt{n}·\sqrt{m}*logn)\\ \end{aligned}$$

代码：

    void solve(){
        int n,m;cin>>n>>m;
        int ans=0;
        for(int i=1;i<=n/i;i++){
            for(int j=1;j<=m/j;j++){
                if(__gcd(i,j)==1)
                ans+=min(n/i,m/j)/(i+j);
            }
        }
    }