soj1748快速求解两数的公因数的个数.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 77 行

#include<stdio.h>
#include<math.h>

const int MAX = 1000001;

int a[MAX];

int next(int i)
{
    int j=i+1;
    while(a[j]==1&&j<MAX)
        j++;
    return j;
}
void primelist(void)
{
    int i,j,k;
    for(i=2;i*i<MAX;i=next(i))
    {
        for(j=i;j*i<MAX;j=next(j))
        {
            for(k=i*j;k<MAX;k*=i)
            {
                a[k]=1;
            }
        }
    }
    for(i=2,j=0;i<MAX;i++)
    {
        if(!a[i])
            a[j++]=i;
    }
}

int gcd(int a,int b)
{
    while(b!=0)
    {
        int t=a;
        a=b;
        b=t%b;
    }
    return a;
}

int main(void)
{
    int n,m;
    int t;
    primelist();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int maxgcd=gcd(n,m);
        int i;
        int sum=1;
        int n=sqrt(maxgcd);
        for(i=0;a[i]<=n;i++)
        {
            int r=0;
            while(maxgcd%a[i]==0)
            {
                r++;
                maxgcd/=a[i];
            }
            sum*=r+1;
            n=sqrt(maxgcd);
        }
        if(maxgcd!=1)
            sum*=2;
        printf("%d\n",sum);
    }
    return 0;
}