1 条题解
-
0
【本题解由站长编写】
x 必须整除 b1(lcm(x,b0)=b1 的必要条件),所以枚举 b1 的约数:d 扫到 √b1,对每个满足整除的 d 同时检查 d 与 b1/d。先做 x%a1 的廉价预筛再做两个 gcd;b1≤2×10⁹ 用 32 位除法加速即可通过 n≤2000。
代码(C++17)
#include <bits/stdc++.h> using namespace std; long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } bool check(long long x, long long a0, long long a1, long long b0, long long b1) { if (x % a1) return false; if (gcd(x, a0) != a1) return false; long long g = gcd(x, b0); return x / g * b0 == b1; } int main() { int n; scanf("%d", &n); while (n--) { long long a0, a1, b0, b1; scanf("%lld %lld %lld %lld", &a0, &a1, &b0, &b1); unsigned b = (unsigned)b1; unsigned lim = (unsigned)sqrt((double)b); while ((unsigned long long)(lim + 1) * (lim + 1) <= b) lim++; long long cnt = 0; for (unsigned d = 1; d <= lim; d++) if (b % d == 0) { if (check(d, a0, a1, b0, b1)) cnt++; if ((unsigned long long)d * d != b && check(b1 / d, a0, a1, b0, b1)) cnt++; } printf("%lld\n", cnt); } return 0; }
- 1
信息
- ID
- 4248
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 0
- 上传者