LOJ #2589. 「NOIP2009」Hankson 的趣味题

趣味题"/>

LOJ #2589. 「NOIP2009」Hankson 的趣味题

题目链接：传送门

分析题目要求， g c d ( x , a 0 ) = a 1 gcd(x,a_0)=a_1 gcd(x,a0​)=a1​， l c m ( x , b 0 ) = b 1 lcm(x,b_0)=b_1 lcm(x,b0​)=b1​
也就是说 a 1 a_1 a1​是 x x x的因子， x x x是 b 1 b_1 b1​的因子
直接 n \sqrt n n ​枚举 x x x（也就是 b 1 b_1 b1​的因子），另外一个 x x x就是 b 1 x \frac{b1}{x} xb1​
然后满足上面两个条件的就 a n s + + \small{ans++} ans++，注意判断 x x x和 b 1 x \frac{b1}{x} xb1​相等的情况
毫无技术含量

#include <bits/stdc++.h>int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
int lcm(int a, int b) {return a / gcd(a, b) * b;}int main(int argc, char const *argv[]) {int T, a0, a1, b0, b1; std::cin >> T;while (T--) {scanf("%d%d%d%d", &a0, &a1, &b0, &b1);int kn = sqrt(1.0 * b1), ans = 0;for (int i = 1; i <= kn; i++)if (b1 % i == 0) {if (gcd(i, a0) == a1 and lcm(i, b0) == b1) ans++;if (i != b1 / i and gcd(b1 / i, a0) == a1 and lcm(b1 / i, b0) == b1) ans++;}printf("%d\n", ans);}return 0;
}