https://www.acwing.com/problem/content/202/
题意：
已知正整数a0,a1,b0,b1，设某未知正整数x满足：
1、 x和a0的最大公约数是a1； 2、 x和b0的最小公倍数是b1。
求有多少个这样的x
数据范围
1≤n≤2000 1≤a0,a1,b0,b1≤2e9
对于一个1e9以内的自然数，其约数最多有1536个
可以先从lcm入手，已知x是b1的约数，那么我们可以将b1的所有约数处理出来，然后逐一判断是否符合条件
假如用暴力的方法，从1到sqrt(b1)的检查是否为b1的约数，会超时，因为一个数的约数个数不会很多，因此可以先将它的素因子处理出来
因此先处理小于sqrt(b1)的素数，找到b1的素因子，然后利用素因子求出b1的约数。
注意b1有可能具有一个大于sqrt(n)的素因子（不可能有两个或者以上了），在预处理b1的素因子的时候需要注意一下
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long using namespace std; const int INF = 0x3f3f3f3f; // sqrt(2e9)<45000 const int maxn = 45000; int prime[maxn], flag[maxn]; int find_prime(int num) { int cnt = 0; for (int i = 2; i <= num; i++) { if (!flag[i]) prime[cnt++] = i; for (int j = 0; j < cnt&&i*prime[j] <= num; j++) { flag[i*prime[j]] = 1; if (i%prime[j] == 0)break; } } return cnt; } ll a0, a1, b0, b1; typedef pair<int, int> P; vector<P> p; vector<ll> V; //里面放约数 void init() { p.clear(); V.clear(); } void dfs(int i, ll now) { if (i >= p.size()) { V.push_back(now); return; } ll sto = 1LL; for (int j = 0; j <= p[i].second; j++) { dfs(i + 1, now*sto); sto *= (ll)p[i].first; } } inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; } int main() { int siz = find_prime(maxn - 1);//预处理素数 int t; cin >> t; while (t--) { init(); cin >> a0 >> a1 >> b0 >> b1; ll sto = b1; int i = 0, cnt; while (sto > 1 && i < siz) { cnt = 0; while (sto % (ll)prime[i] == 0) { cnt++; sto /= (ll)prime[i]; } if (cnt) p.push_back(P(prime[i], cnt)); i++; } if (sto > 1) p.push_back(P((int)sto,1));//可能有大于sqrt（b1）的素因子 dfs(0, 1);//dfs求约数 int ans = 0; for (int j = 0; j < V.size(); j++) {//逐个判断 if (gcd(V[j], a0) == a1 && lcm(V[j], b0) == b1) ans++; } cout << ans << endl; } return 0; }
