洛谷p1072 gcd，质因数分解

/*
可以得a>=c,b<=d，枚举d的质因子p
那么a,b,c,d,x中包含的p个数是ma,mb,mc,md,mx
在gcd(a,x)=c中
    ma<mc => 无解 
    ma=mc => mx>=mc
    ma>mc => mx=mc 
在lcm(b,x)=d中
    mb<md => mx=md 
    mb=md => mx<=md
    mb>md => 无解 
那么
ma==mc且mb==md时，mc<=mx<=md
ma>mc时 mx=mc,mb<md时，mx=md 
令cntp表示x包含质因子p的方案数 
预处理质数，找出所有d的质因子p，计算cntp，如果d自己也是质数，那么计算一次cntd即可
复杂度O(nsqrt(d)/logd) 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll a,b,c,d,x,ma,mb,mc,md,mx,tot,p[1000000];
ll m,prime[1000000],v[1000000];
void init(int n){
    memset(v,0,sizeof v);
    m=0;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }    
}
int divide(int n,int p){
    int res=0;
    while(n%p==0)res++,n/=p;
    return res;
}

int main(){
    init(sqrt(2000000007));//打表 
    int n;
    scanf("%d",&n);
    while(n--){
        ll ans=1,cnt,tot=0,flag=0;
        scanf("%lld%lld%lld%lld",&a,&c,&b,&d);
        int tmp=d;
        for(int i=1;i<=m;i++){//求出d的所有质因子 
            if(prime[i]>d) break;
            if(d%prime[i]==0) {
                p[++tot]=prime[i];
                while(d%prime[i]==0) d/=prime[i];
            }
        }
        if(d>1)p[++tot]=d;
        
         d=tmp;
        for(int i=1;i<=tot;i++){
            ma=divide(a,p[i]);
            mb=divide(b,p[i]);
            mc=divide(c,p[i]);
            md=divide(d,p[i]);
            if(ma<mc || mb>md)ans=0;//不可能的情况 
            else if(ma==mc && mb==md){//两者都有多解 
                if(mc<=md) ans*=(md-mc+1);
                else ans=0;
            }
            else if(ma==mc && mb<md){//只有一解，可能没有 
                if(mc>md) ans=0;
            }
            else if(mb==md && ma>mc){
                if(mc>md)ans=0;
            }
            else if(mc!=md) ans=0; 
                    
            if(ans==0) break;
        }
        printf("%lld\n",ans);
    }    
}

这是进阶指南第一版的一道题，书上有个推论错了，，