题解 P1072 【Hankson 的趣味题】

2019-09-27 14:41:34


这道题是一道入门数学题

用线性筛筛出sqrt(2000000000)质数

枚举b1的质因子

用dfs求出每一个约数

根据。。。。一个int的约数最多有1536个

所以直接判断即可

因为我搜的时候

第一个裸质因数可能重复

所以用Map来解决重复问题就结束了

时间复杂度上限O(T1536log(1536))

//code by luotc

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
    return x*f;
}

const int maxn=1e6+5;

int n,prime[maxn],v[maxn],cnt,tot[maxn],cnt1,a[maxn],cnt2,a0,a1,b0,b1,ans;

inline void shaifa(int n){
    for(int i=2;i<=n;i++){
        if(!v[i]){
            v[i]=1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
            v[prime[j]*i]=prime[j];
            if(i%prime[j]==0) break; 
        }
    }
}

inline int gcd(int x,int y){
    if(x%y==0) return y;
    else return gcd(y,x%y);
}

inline void dfs(int dep,int sum){
    if(b1%sum!=0) return;
    a[++cnt2]=sum;
    dfs(dep,sum*tot[dep]);
    if(dep+1>cnt1) return;
//  dfs(dep+1,sum*tot[dep+1]);
    dfs(dep+1,sum);
}

signed main(){
    n=read();
    shaifa(1000000);
    for(int i=1;i<=n;i++){
        map<int,int> Map;
        a0=read(),a1=read(),b0=read(),b1=read();
        int x=b1;cnt1=0;cnt2=0;ans=0;
        for(int j=1;j<=cnt;j++){
            if(prime[j]*prime[j]>b1) break;
            if(b1%prime[j]==0){
                tot[++cnt1]=prime[j];
            }
        }
        for(int j=1;j<=cnt1;j++) while((x!=1)&&(x%tot[j]==0)) x/=tot[j];
        if(x!=1) tot[++cnt1]=x;
        if(cnt1!=0) dfs(1,1);
        else a[++cnt2]=1;
//      for(int j=1;j<=cnt1;j++){
//          cout<<tot[j]<<" ";
//      }
//      cout<<endl;
//      for(int j=1;j<=cnt2;j++){
//          cout<<a[j]<<"  ";
//      }
        for(int j=1;j<=cnt2;j++){
            if(Map[a[j]]) continue;
            Map[a[j]]=1;
            int x=gcd(a0,a[j]);
            if(x!=a1) continue;
            x=gcd(a[j],b0);
            if(b0*a[j]/x!=b1) continue;
            ans++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

还记得去年被此题吊打。。。