Pair Number Mystery

Problem Statement

给定两个正整数 $ X $ 和 $ Y $，请你找出所有满足以下条件的有序整数对 $ (A, B) $（其中 $ A $ 和 $ B $ 均为正整数）：

$ A - B = X $

$ \frac{\text{lcm}(A, B)}{\text{gcd}(A, B)} = Y $

输出所有满足条件的 $ (A, B) $。如果有多个 $ (A, B) $ 满足条件，按 $ A $ 的大小升序输出。

Input

本题有多个测试数据。第一行一个整数 $ T $，表示测试数据的组数。接下来 $ T $ 行，每行包含两个正整数 $ X $ 和 $ Y $，含义如上所述。

Output

对于每组数据，先输出一个整数 $ K $，表示满足条件的 $ (A, B) $ 的方案数。接下来 $ K $ 行，每行输出两个用空格隔开的正整数 $ A $ 和 $ B $，表示一个满足条件的解。如果没有解，仅输出一行 0。

Solving

设 $gcd(A,B) = d$

则 $ A = a * d,B = b * d$

其中$gcd(a,b) == 1$

将其带入$ \frac{\text{lcm}(A, B)}{\text{gcd}(A, B)} = Y $ 中得： Y = a * b

将其带入$ A - B = X $ 得 $d = X / (a - b)$

所以我们只需要求出满足上述条件的(a,b)的对数即可

枚举a，判断a是否被Y整除，随后整除出b再判断其最大公因数是否为1，随后判断其(a-b)是否可以被X整除，如果上述条件均满足则表示其数对满足条件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


void solve()
{
    int x,y;
    cin >> x >> y;
    vector<pii> ans;
    // a * b == y and gcd(a,b) == 1, gcd(A,B) == x / (a-b)
    for(int a=1;a*a<=y;a++)
    {
        if(y % a == 0)
        {
            int b = y / a;
            if(__gcd(a,b) == 1)
            {
                if(a > b)
                {
                    int gap = a - b;
                    if(x % gap == 0)
                    {   
                        int d = x / gap;
                        ans.push_back({a*d,b*d});
                    }
                }
                if(b > a)
                {
                    int gap = b - a;
                    if(x % gap == 0)
                    {   
                        int d = x / gap;
                        ans.push_back({b*d,a*d});
                    }
                }
            }
        }
    }
    sort(ans.begin(),ans.end());
    if(ans.empty())
    {
        cout << 0 << endl;
        return;
    }
    cout << ans.size() << endl;
    for(auto [A,B] : ans)
    {
        cout << A << ' ' << B << endl;
    }
}