算法竞赛进阶指南，143页，素数
本题要点：
1、gcd(a, x) = c, lcm(b, x) = d。 因为x是d的约数，x的素因子也是d的素因子。
对于d的每一个素因子， ma, mb, mc, md, mx 分别表示a, b, c, d, x中含有的素因子个数.
2、因为最大公约数 gcd(a, x) = c, 因此
a）ma > mc, mx 只能等于 mc
b）ma == mc, mx >= mc即可
c）ma < mc, 无解
3、 因为最小公倍数 lcm(b, x) = d, 因此
a）mb < md, mx 只能等于 md
b）mb == md, mx <= md 即可
c）mb > md, 无解
4、 综合以上分析，分类讨论：
a）ma > mc && mb < md && mc == md
mx == mc == md, 只有一种情况
b）ma > mc && mb == md && mc <= md
mx == mc， 只有一种情况
c）ma == mc && mb < md && mc <= md
mx == md, 只有一种情况
d）ma == mc && mb == md && mc <= md
mx 取 mc 到 md之间的任意值， 有 md - mc + 1 中选择
e）其他情况无解
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int MaxN = 50010;
int a, c, b, d, T;
int vis[MaxN]; // vis[i] 存放的是 数i的最小的素因子，当 vis[i] == i, 说明i是素数
int prime[MaxN];
int pNum; //质数的数量
int fac[11]; //质因子
int m;void prime_init(int n)
{
memset(vis, 0, sizeof vis);pNum = 0;for(int i = 2; i <= n; ++i){
if(!vis[i]){
vis[i] = i;prime[++pNum] = i; // i是素数}//给当前的数i乘以一个质因子for(int j = 1; j <= pNum; ++j){
if(prime[j] > vis[i] || prime[j] > n / i)break;vis[i * prime[j]] = prime[j];}}
}int calc(int a, int p)
{
if(a < p)return 0;int s = 0;while(a % p == 0){
a /= p;++s;}return s;
}void solve()
{
int mark_d = d;m = 0;long long ans = 1;for(int i = 1; prime[i] <= d && i <= pNum; ++i){
if(d % prime[i] == 0){
fac[++m] = prime[i];while(d % prime[i] == 0)d /= prime[i];}}if(d > 1)fac[++m] = d;int ma, mb, mc, md;for(int i = 1; i <= m; ++i){
int cnt = 0;ma = calc(a, fac[i]), mb = calc(b, fac[i]), mc = calc(c, fac[i]), md = calc(mark_d, fac[i]); if(ma > mc && mb < md && mc == md)++cnt;if(ma > mc && mb == md && mc <= md)++cnt;if(ma == mc && mb < md && mc <= md)++cnt;if(ma == mc && mb == md && mc <= md){
cnt += md - mc + 1;}ans *= cnt;}printf("%lld\n", ans);
}int main()
{
prime_init(50000); scanf("%d", &T);while(T--){
scanf("%d%d%d%d", &a, &c, &b, &d);solve();}return 0;
}/* 2 41 1 96 288 95 1 37 1776 *//* 6 2 */