趣味题"/>
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;
}
更多推荐
LOJ #2589. 「NOIP2009」Hankson 的趣味题
发布评论