算法分析

朴素做法

题目中讲述到：x和a0的最大公约数是a1，x和b0的最小公倍数是b1，因此可以得到下面两条方程
$$\begin{cases} gcd(x,a_0) = a_1， \frac{x * b_0}{gcd(x,b_0)} = b_1\\ \end{cases}$$

对于每组样例，共有T个样例，对于每个样例，枚举b1的所有约数，即for(int i = 1;i <= b1 / i;i ++),此操作的复杂度是$O(\sqrt n)$，对于每个约数进行gcd，和lcm操作，此操作的时间复杂度是$O(logn)$，因此总的时间复杂度是$O(T * logn * \sqrt n)$

估算一下，$2000$组样例数据，最大取到$2 * 10^9$,$log(2 * 10^9) = 10$，$\sqrt {2 * 10^9} = 44721$，因此$2000 * 10 * 44721 = 894,420,000 > 10^8$，会超时,卡一个数据

优化后做法

对于枚举b1的所有约数，即for(int i = 1;i <= b1 / i;i ++),此操作的复杂度是$O(\sqrt n)$，可以先预处理出 $b1$ 的所有约数，再枚举约数，而不需要从1开始枚举到 $\sqrt b1 $，预处理 $ b1$ 的所有约数的方法是筛出1到$\sqrt b1$的所有质因子，特别地，若 $b1$ 是一个质数，也需要筛出来，再通过dfs把所有约数都找出来

由于1 到 n中质数的个数是$\frac{n}{lnn}$个，因此枚举b1的所有约数的时间复杂度是$\frac{\sqrt b1}{ln\sqrt b1}$，因此总的时间复杂度是$O(T * logn * \frac{\sqrt b1}{ln\sqrt b1})$，大概运行$42000 * 10 * 44721 / 21 = 42,591,428次 < 10 ^ 8$

时间复杂度$O(T * logn * \frac{\sqrt b1}{ln\sqrt b1})$

参考文献

算法提高课

Java 代码（朴素版）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int gcd(int a,int b)
    {
        return b == 0 ? a : gcd(b , a % b);
    }
    static int lcm(int a,int b)
    {
        return (int) ((long)a * b / gcd(a,b));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine().trim());
        while(T -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            int a0 = Integer.parseInt(s1[0]);
            int a1 = Integer.parseInt(s1[1]);
            int b0 = Integer.parseInt(s1[2]);
            int b1 = Integer.parseInt(s1[3]);

            int res = 0;
            for(int i = 1;i <= b1 / i;i ++)
            {
                if(b1 % i != 0) continue;
                if(gcd(a0,i) == a1 && lcm(b0,i) == b1)
                    res ++;
                if(i != b1 / i && gcd(a0,b1 / i) == a1 && lcm(b0,b1 / i) == b1)
                    res ++;
            }
            System.out.println(res);
        }
    }
}

Java 代码（优化版）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 50010;
    static int cnt = 0;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static Pair[] pair = new Pair[10];//最多只用到9个质因子
    static int fcnt;
    static int[] divisor = new int[1601];
    static int dcnt;
    static void init(int n)
    {
        for(int i = 2; i <= n;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    //u表示枚举到当前质因子，p表示当前的值
    static void dfs(int u,int p)
    {
        if(u == fcnt)
        {
            divisor[dcnt ++] = p;
            return ;
        }
        for(int i = 0;i <= pair[u].s;i ++)
        {
            if(i == 0) dfs(u + 1,p);// 选择0个
            else {p *= pair[u].p; dfs(u + 1,p);}
        }
    }
    static int gcd(int a,int b)
    {
        return b == 0 ? a : gcd(b,a % b);
    }
    static int lcm(int a,int b)
    {
        return (int) ((long)a * b / gcd(a,b));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine().trim());
        init(N - 1);
        while(T -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            int a0 = Integer.parseInt(s1[0]);
            int a1 = Integer.parseInt(s1[1]);
            int b0 = Integer.parseInt(s1[2]);
            int b1 = Integer.parseInt(s1[3]);

            int t = b1;
            fcnt = 0;
            //对t进行分解t = p0^c0 * p1^c1 * ... * pk^ck
            for(int i = 0;primes[i] <= t / primes[i];i ++)
            {
                if(t % primes[i] == 0)
                {
                    int s = 0;
                    while(t % primes[i] == 0)
                    {
                        t /= primes[i];
                        s ++;
                    }
                    pair[fcnt ++] = new Pair(primes[i],s);
                }
            }
            if(t > 1) pair[fcnt ++] = new Pair(t,1);

            //找出出所有的约数
            dcnt = 0;
            dfs(0,1);

            //枚举所有的约数，判断哪个约数成立
            int ans = 0;
            for(int i = 0;i < dcnt;i ++)
            {
                int x = divisor[i];
                if(gcd(x,a0) == a1 && lcm(x,b0) == b1) ans ++;
            }
            System.out.println(ans);
        }


    }
}
class Pair 
{
    int p,s;
    Pair(int p,int s)
    {
        this.p = p;
        this.s = s;
    }
}