记录编号 |
44142 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2009]Hankson的趣味题 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.062 s |
提交时间 |
2012-10-16 22:16:24 |
内存使用 |
0.50 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEP=50000;
int p[SIZEP]={0};
long a0,a1,b0,b1,sum=1,low=0,high=0;
int inda0,inda1,indb0,indb1;
void prime(void){//筛法生成素数
bool l[SIZEP]={0};
int i,j,k=0,temp;
temp=(int)sqrt((double)SIZEP);
for(i=2;i<SIZEP;i++){
if(!l[i]){//素数
p[k]=i,k++;
if(i<=temp){
for(j=i*i;j<=SIZEP;j+=i) l[j]=1;
}
}
}
}
int getind(long *a,long p){//a的分解中有几个p
int sum=0;
while(*a%p==0){
*a/=p,sum++;
}
return sum;
}
void reckon(int pi){
inda0=getind(&a0,pi),inda1=getind(&a1,pi);
indb0=getind(&b0,pi),indb1=getind(&b1,pi);
low=inda1;
if(indb0<indb1) low=indb1;
high=indb1;
if(inda0>inda1) high=inda1;
if(high>=low) sum*=(high-low+1);
else sum=0;
}
int deal(void){
sum=1,low=0,high=0;
int i;
cin>>a0>>a1>>b0>>b1;
for(i=0;p[i]*p[i]<=b1&&p[i]!=0;i++){
reckon(p[i]);
}
if(b1>1) reckon(b1);
return sum;
}
int main(){
freopen("son.in","r",stdin);
freopen("son.out","w",stdout);
prime();
int n,i;
cin>>n;
for(i=1;i<=n;i++){
cout<<deal()<<endl;
}
return 0;
}