记录编号 |
40506 |
评测结果 |
AAAAAAAAAA |
题目名称 |
最大公约数 |
最终得分 |
100 |
用户昵称 |
TBK |
是否通过 |
通过 |
代码语言 |
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;
}