算法分析

50pts

[1]因为有50%的数据保证$b_1 \leq 10^4$,而这些$x$一定是小于等于$b1$的,所以我们可以直接枚举$x$的范围是1到$b_1$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
	return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		LL a0,a1,b0,b1;
		cin>>a0>>a1>>b0>>b1;
	//	int p=a0/a1,q=b1/b0;
		int ans=0;
		for(int x=1;x<=b1;x++) //枚举小因子 
		{
			if(b1%x==0) //x是b1的因子 
			{
				if(gcd(x,a0)==a1&&lcm(x,b0)==b1) //x是a1的倍数
				{  //a1是x和a0的最大公约数  b1是x和b0的最小公倍数
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

90pts

由于$b_1$是$10^9$次方，这样$nb_1$一定会超时，我们可以枚举较小的因子，然后算出来较大的因子时间复杂度会变成$nb_1log^{b_1}$,这样的话只有一个点超时了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
	return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		LL a0,a1,b0,b1;
		cin>>a0>>a1>>b0>>b1;
	//	int p=a0/a1,q=b1/b0;
		int ans=0;
		for(int x=1;x<=b1/x;x++) //枚举小因子 
		{
			if(b1%x==0) //x是b1的因子 
			{
				if(x%a1==0&&gcd(x,a0)==a1&&lcm(x,b0)==b1) //x是a1的倍数
				{  //a1是x和a0的最大公约数  b1是x和b0的最小公倍数
					ans++;
				}
				int y=b1/x;//大因子 
				if(x==y) continue; //同一个数
				if(y%a1==0&&gcd(y,a0)==a1&&lcm(y,b0)==b1) //x是a1的倍数 //同理可得
				{
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

100pts

这样还是会比较慢，主要是枚举约数这个部分，然后我们可以通过枚举分解质因数求约数，然后得到对应的约数再进行枚举，这样的话就可以完美通过这个题目了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=45000,M=50;
int primes[N],cnt;
bool st[N];
PII factor[N];
int cntf;
int divider[N],cntd;
void get_primes(int n) //线性筛质数
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[i*primes[j]]=true;
            if(i%primes[j]==0) break;
        }
    }
}
int gcd(int a,int b) //最大公约数
{
    return b?gcd(b,a%b):a;
}
void dfs(int u,int p) //通过dfs找到所有的约数
{
    if(u>cntf) //枚举完了，说明当前数是一个合法的约数
    {
        divider[cntd++]=p;
        return ;
    }
    for(int i=0;i<=factor[u].second;i++) //枚举当前因子所选的因子个数
    {
        dfs(u+1,p);
        p*=factor[u].first;//累乘
    }
}
int lcm(int a,int b) //最小公倍数
{
    return (LL)a*b/gcd(a,b);
}
int main()
{
    get_primes(N);
    int n;
    cin>>n;
    while(n--)
    {
        int a0,a1,b0,b1;
        cin>>a0>>a1>>b0>>b1;
        int d=b1;
        cntf=0;//质因子的个数
        for(int i=0;primes[i]<=d/primes[i];i++) //分解质因数
        {
            int p=primes[i];
            if(d%p==0)
            {
                int s=0;
                while(d%p==0) s++,d/=p;
                factor[++cntf]={p,s};
            }
        }
        if(d>1) factor[++cntf]={d,1}; //剩余的d本身是一个较大的质数
        
        cntd=0;
        dfs(1,1); //搜索所有约数
        
        int res=0;
        for(int i=0;i<cntd;i++) //枚举所有约数
        {
            int x=divider[i];
            if(gcd(x,a0)==a1&&lcm(x,b0)==b1)
            {
                res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}