原题链接:https://www.luogu.com.cn/problem/P1072
题意解读:求有多少个x,满足x和a0 的最大公约数是a1,x和b0的最小公倍数是b1,多组数据。
解题思路:
枚举法:
因为x和a0 的最大公约数是a1,x和b0的最小公倍数是b1,所以x不大于b1。
枚举x有两种思路:
1、x是a1的倍数,最多需要枚举b1/a1次,如果a1=1,最多b1次,10^9规模,有2000组数据,超时。
2、x是b1的因数,最多需要枚举sqrt(b1)次,也就是x * x <= b1即可,10^4规模,2000组数据,可行。
因此,可以枚举b1的因数,每次枚举可以得到两个因数:x、b1/x,进行判断即可。
100分代码:
#include <bits/stdc++.h>
using namespace std;
long long n, a0, a1, b0, b1;
long long gcd(long long a, long long b)
{
if(b == 0) return a;
return gcd(b, a % b);
}
int main()
{
cin >> n;
while(n--)
{
int ans = 0;
cin >> a0 >> a1 >> b0 >> b1;
for(long long x = 1; x * x <= b1; x++) //枚举b1的所有因子,每次可以考察i、b1/i两个,循环次数sqrt(b1)
{
if(b1 % x == 0)
{
if(gcd(x, a0) == a1 && x * b0 == gcd(x, b0) * b1)
{
ans++;
}
long long y = b1 / x;
if(x == y) continue;
if(gcd(y, a0) == a1 && y * b0 == gcd(y, b0) * b1)
{
ans++;
}
}
}
cout << ans << endl;
}
return 0;
}
注意gcd()的判断前提是x是b1的因子,实际的因子数2*10^9也只有110个,所以gcd的调用复杂度可以忽略,总体复杂度就是10^7规模。
标签:gcd,洛谷题,NOIP2009,long,a1,枚举,b0,b1,P1072 From: https://www.cnblogs.com/jcwy/p/18129799