[NANKAI 2080]质因数分解、dfs构造数

传送门

【题目大意】

给定x和a0的最大公约数是a1

x和b0的最小公倍数是b1

求存在多少个符合条件的x

【算法分析】

哎，NOIP第2题，当时只拿50分。。。

在景润后人的指导下，发现原来这么简单。。。原来我当时捉错方向了。

题目相当于给出两个条件：

根据第一个条件去构造的话，只能根据x=k*a0直接枚举。极限数据的话这必然TLE。

然后如果根据第二个条件去构造的话，就可以根据质因子来dfs，虽然也比较暴力，但是明显比上面那个好很多。。。

于是我们可以对b0质因数分解，枚举构造b0/gcd(b0,x)的这个部分，然后再用b1得到x，再判定就行了。

【其它】TLE多次，最终分解质因数那里改了一下，终于AC。

YM best user 景润后人 AekdyCoin

95562 AekdyCoin 2080 Accepted GNU C++ 1.46k 40ms 1312KB 2009-11-22 14:39:10 95729 xiaotian 2080 Accepted Free Pascal 3.39k 60ms 416KB 2009-11-24 13:31:02 96022 nehzilrz(2) 2080 Accepted GNU C++ 1.10k 60ms 768KB 2009-11-28 11:08:08 99216 edward 2080 Accepted GNU C++ 1.36k 60ms 1536KB 2010-02-12 18:22:38

【CODE】

#include #include const int N=50001;
int ss[N],a0,a1,b0,b1,ssl[N],sst;
int sl[N],num[N],len,ans;

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

void makess(){
    sst=0;
    ss[1]=1;
    for (int i=2;i*i<=N;i++) if (!ss[i])
      for (int j=i;i*j<=N;j++)
        ss[i*j]=1;
    for (int i=1;i<=N;i++)
      if (ss[i]==0){
          sst++;
          ssl[sst]=i;
      }   
}   

void fenjie(int n){
    len=0;
    for (int i=1;n!=1 && n>=ssl[i] && i<=sst;i++)
      if (n%ssl[i]==0){
          len++;
          sl[len]=ssl[i];
          num[len]=0;
          while (n%ssl[i]==0){
              n/=ssl[i];
              num[len]++;
          }   
      }   
    if (n!=1){
        len++;
        sl[len]=n;
        num[len]=1;
    }   
}   

void dfs(int i,int now){
    if (i>len){
        int x=b1/now;
        int t=gcd(x,b0),tmp=x/t*b0;
        if (gcd(x,a0)!=a1 || x/gcd(x,b0)*b0!=b1) return;
        ans++;
        return;
    }
    dfs(i+1,now);
    for (int k=1;k<=num[i];k++){
        now*=sl[i];
        dfs(i+1,now);
    }   
}   

int main(){
    makess();
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        fenjie(b0);
        ans=0;
        dfs(1,1);
        printf("%dn",ans);
    }   
}