求出所有的正整數對 使他們最大公約數為n，最小公倍數為m

求出所有的正整數對 使他們最大公約數為n，最小公倍數為m

大意就是 求出所有的正整數對 使他們最大公約數為n，最小公倍數為m。（1 <= n, m <= 10^10）

可以將問題轉化為 ： 設a，b就是那個整數對，n, a, b, m, 這4個數都是可以被n整除的，可以都除以n， 題目轉化為求出 最大公約數為1， 最小公倍數為m/n的對數 。

也就是求出在1到m/n裡 乘積為m/n且互質的對數。可以在O(sqrt (m/n) )內解決。

#include 
#include 
#include 
#include 
#include 
#include 
#define MAX 0x3f3f3f3f
#define N 2000005
typedef long long LL;
using namespace std;

int T;
LL n, m;
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    cin>>T;while(T--) {
        cin >> n >> m;
        if(m % n) {
            printf(0
);
            continue;
        }
        LL x = m / n;
        int ans = 0;
        for(LL i = 1; i <= (LL)sqrt(x); i++) {
            if(x % i == 0) {
                LL j = x / i;
                if(gcd(i, j) == 1) ans++;
            }
        }
        printf(%d
, ans);
    }
    return 0;
}