记录编号 44142 评测结果 AAAAAAAAAA
题目名称 [NOIP 2009]Hankson的趣味题 最终得分 100
用户昵称 Gravatarcstdio 是否通过 通过
代码语言 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;
}