http://www.bnuoj.com/bnuoj/contest_show.php?cid=613#problem/7494

一开始我都没有读懂题意,在理解题意上花费了很多时间,最终理解是A的所有质因子都是B的质因子,B的质因子不一定是A的

#include “stdio.h”
#include “string.h”
#include “math.h”
#define num 2000000
int x[num],prime[5000000];
void allprime()   //打印素数表
{
int cnt=0,i,j;
memset(x,0,sizeof(x));
for(i=2;i<num;i++)
{
if(!x[i])
prime[cnt++]=i;
for(j=0;(j<cnt) && (i*prime[j]<num);j++)
{
x[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
int n,cases=1,flag,i,j,x;
__int64 a,b;
scanf(“%d”,&n);
allprime();
while(n–)
{
scanf(“%I64d%I64d”,&a,&b);
flag=1;
for(i=0;prime[i]<=(int)sqrt(a) && prime[i];i++)
{
x=prime[i];
if(a%x==0)
{
if(b%x!=0)
{
flag=0;
break;
}
while(a%x==0)
a/=x;
}
}
if(a!=1 && b%a!=0)
flag=0;
printf(“Case #%d: “,cases++);
printf(flag?”YES\n”:”NO\n”);
}
return 0;
}
That’s all!

发表评论

电子邮件地址不会被公开。

Post Navigation