洛谷 P1072 【Hankson 的趣味题】

题库：洛谷
题号：1072
题目：Hankson 的趣味题
link：https://www.luogu.com.cn/problem/P1072

这题看起来很难其实很简单，只需要暴力就能算出来，复杂度$O(n$ $√b1$ $log(√b1))$，能跑过去。

由题意得：

$gcd(x, a0) = a1$；

$lcm(x, b0) = b1$；

这就说明$x$是$a1$的整数倍，且$x$是$b1$的因子。

那么我们只需要枚举$b1$的因子然后判断是否是$a1$的整数倍且满足上面的一个$gcd$和一个$lcm$。

但因为枚举$b1$的因子复杂度太高，所以可以枚举到 $√b1$ 然后通过$b1$除以这个因子得到另一个因子。

但注意当$x * x = b$1时，两个因子的答案加一次就行了。

$code：$

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define ll long long
 4 using namespace std;
 5 int T, a0, a1, b0, b1;
 6 int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 7 ll lcm(int a, int b) {return 1ll * a * b / gcd(a, b);}
 8 int main()
 9 {
10     scanf("%d", &T);
11     while(T--)
12     {
13         int ans = 0;
14         scanf("%d %d %d %d", &a0, &a1, &b0, &b1);
15         for(int i = 1; i * i <= b1; ++i)
16         {
17             if(b1 % i != 0) continue;
18             if(i % a1 == 0 && gcd(i, a0) == a1 && lcm(i, b0) == 1ll * b1) ++ans;
19             if(i * i == b1) continue;
20             int j = b1 / i;
21             if(j % a1 == 0 && gcd(j, a0) == a1 && lcm(j, b0) == 1ll * b1) ++ans;
22         }
23         printf("%d
", ans);
24     }
25     return 0;
26 }