学步园

基本思路还OK。。关键是我直接分解质因数 弄组合去了。。（而且我分解质因数由于素数打表有阴影，

从未成功实现过，所以我分解质因数开始也写的暴力十足= =）

没想到直接  k1、k2 互质，然后直接数个数n,输出2^n.

最后百无聊赖，各种搞不好，导致我去弄gcd函数暴力，很明显的超时。。

关键时刻我能说我 求最大公约数怎么写都忘了么T^T....我。。。

官方题解啦~

第6题：gcd和lcm

本题为基本数学题。

分析设a=k1*x,b=k2*x.则gcd(k1,k2)=1.且y=k1*k2*x 则k1*k2=y/x.

由于k1,k2互质，所以可以可以将y/x分解质因数。假设y/x=a1^b1*a2^b2*a3^b3….*an^bn

显然如果k1含有质因子ai,则k2一定不含因子ai,如果k1,k2同时含有相同因子的话，他们就不互质，可以推出矛盾。

所以k1,k2只可能含不同质因子，故只用统计y/x的质因子个数就可以了。

其种数为C(n,0)+C(n,1)+C(n,2)+…+C(n,n)=2^n.

解法：

用用o(n*lgn*lgn)的素数筛选法筛选素数，然后分解质因数，求出质因数个数n,最后输出2^n即可。总的时间复杂度o(n*lgn*lgn).

注意x不整除y的情况，直接输出0.

#include<cstdio>
#include<iostream>
#include<cstring>
#define M 1000010
using namespace std;

int s[32],cnt;
int isprime[M],prime[M];

void init()
{
    s[0]=1;
    for(int i=0;i<=30;i++)
        s[i+1]=s[i]<<1;

    memset(isprime,true,sizeof(isprime));
    int nn=1000000;
    cnt=0;

    for(int i=2;i<=nn;i++)
    {
        if(isprime[i])
        {
            prime[++cnt]=i;
            for(int j=i*2;j<=nn;j+=i)
                isprime[j]=false;
        }
    }
}

int main()
{
    int x,y;
    init();

    while(scanf("%d%d",&x,&y)!=EOF)
    {
        if(y%x)
        {
            printf("0\n");
            continue;
        }
        int t=y/x;
        int sum=0;

        for(int i=1;prime[i]<t && i<cnt;i++)
        {
            if(t%prime[i]==0)
            {
                sum++;
                while(t%prime[i]==0)
                {
                    t=t/prime[i];
                }
            }
        }
        if(t!=1)
            sum++;

        printf("%d\n",s[sum]);
    }
    return 0;
}