记录编号 40506 评测结果 AAAAAAAAAA
题目名称 最大公约数 最终得分 100
用户昵称 GravatarTBK 是否通过 通过
代码语言 C++ 运行时间 0.550 s
提交时间 2012-07-18 09:15:42 内存使用 0.44 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[31000]={2},b,c,d,e,l,m,n=1,r[1000][2],x,y,z[1000];
long long k,t;
void zhishu(void)
{
    for (l=3;l<=40000;l+=2)
    {
        for (m=0;m<n;m++)
            if (l%a[m]==0) break;
        if (m==n) 
        {
            a[n]=l;
            n++;
        }
    }
}
void fenjie(void)
{
    for (l=0;l<n;l++)
    {
        if (d==1) break;
        if (a[l]>(int)pow((double)d,0.5)) 
        {
            if (r[x][0]==0) 
            { 
                r[x][0]=d;
                r[x][1]++;
                x++;
            }
                else if (r[x][0]==d) 
                {
                    r[x][1]++;
                    x++;
                }
                    else
                    {
                        x++;
                        r[x][0]=d;
                        r[x][1]++;
                        x++;
                    }
            break;
        }
        if (d%a[l]==0) 
        {
            if ((a[l]!=r[x-1][0])||(x==0))
            {
                r[x][0]=a[l];
                r[x][1]++;
                d/=a[l];
                l--;
            }
        }
            else if (r[x][0]!=0) x++;
    }
    if (l==n) 
    {
        r[x][0]=d;
        r[x][1]++;
        x++;
    }
}
void yueshu(int y,int h)
{
    int i,j;
    if ((y==x)&&(h>=e)) 
    {
        k=d/h;
        for (j=0;j<x;j++)
            if (z[j]!=0) 
            {
                k/=r[j][0];
                k*=(r[j][0]-1);
            }
        t+=k;
        return;
    }
    if (y==x) return;
    for (i=0;i<=r[y][1];i++) 
    {
        h*=(int)pow((double)r[y][0],(double)i);
        z[y]=r[y][1]-i;
        yueshu(y+1,h);
        h/=(int)pow((double)r[y][0],(double)i);
    }
}
int main(void)
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    scanf("%d",&b);
    zhishu();
    for (c=0;c<b;c++)
    {
        scanf("%d%d",&d,&e);
        x=0;
        y=d;
        k=0;
        for (l=0;l<100;l++)
        {
            r[l][0]=0;
            r[l][1]=0;
        }
        fenjie();
        if (e==y) 
        {
            printf("1\n");
            continue;
        }
        if (e>y) 
        {
            printf("0\n");
            continue;
        }
        if ((e==1)||(e==0)) printf("%d\n",y);
            else
            {
                t=0;
                d=y;
                yueshu(0,1);
                printf("%lld\n",t);
            }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}