记录编号	141622	评测结果	AAAAAAAAAA
题目名称	193.最多因子数	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-12-03 17:45:54	内存使用	0.42 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
const int MAXN=31622;
bool b[31622];
int prime[20000],a[200]={1,2,3,4,6,8,10,12,18,20,24,30,36,48,60,72,84,90,96,108,120,168,180,240,336,360,420,480,504,540,600,630,660,672,720,840,1080,1260,1440,1680,2160,2520,3360,3780,3960,4200,4320,4620,4680,5040,7560,9240,10080,12600,13860,15120,18480,20160,25200,27720,30240,32760,36960,37800,40320,41580,42840,43680,45360,50400,55440,65520,75600,83160,98280,110880,131040,138600,151200,163800,166320,196560,221760,262080,277200,327600,332640,360360,393120,415800,443520,471240,480480,491400,498960,554400,655200,665280,720720,831600,942480,982800,997920,1053360,1081080,1330560,1413720,1441440,1663200,1801800,1884960,1965600,2106720,2162160,2827440,2882880,3326400,3603600,4324320,5405400,5654880,5765760,6126120,6320160,6486480,7207200,8648640,10810800,12252240,12972960,13693680,14137200,14414400,17297280,18378360,20540520,21621600,24504480,27387360,28274400,28828800,30270240,30630600,31600800,32432400,36756720,41081040,43243200,49008960,54774720,56548800,60540480,61261200,64864800,68468400,73513440,82162080,86486400,91891800,98017920,99459360,102702600,107442720,108108000,109549440,110270160,122522400,136936800,147026880,164324160,183783600,205405200,220540320,232792560,245044800,273873600,294053760,328648320,349188840,367567200,410810400,465585120,490089600,497296800,514594080,537213600,547747200,551350800,616215600,698377680,735134400,821620800,931170240,994593600},divsum[200]={1,2,2,3,4,4,4,6,6,6,8,8,9,10,12,12,12,12,12,12,16,16,18,20,20,24,24,24,24,24,24,24,24,24,30,32,32,36,36,40,40,48,48,48,48,48,48,48,48,60,64,64,72,72,72,80,80,84,90,96,96,96,96,96,96,96,96,96,100,108,120,120,120,128,128,144,144,144,144,144,160,160,168,168,180,180,192,192,192,192,192,192,192,192,200,216,216,224,240,240,240,240,240,240,256,256,256,288,288,288,288,288,288,320,320,336,336,360,384,384,384,384,384,384,400,432,448,480,480,480,480,480,504,512,512,512,576,576,576,576,576,576,576,576,600,640,640,672,672,672,672,672,720,720,720,768,768,768,768,768,768,768,768,768,768,800,864,864,896,896,960,960,960,960,1008,1008,1024,1024,1024,1152,1152,1152,1152,1152,1152,1152,1152,1200,1200,1280,1344,1344,1344,1344};
int main(){
	freopen("divisors.in","r",stdin);
	freopen("divisors.out","w",stdout);
	int i,j,x,tot=194,ans,tmpsum,maxans=0,L,R,maxi;
	prime[0]=1;
	for(i=2;i<MAXN;++i){
		if(!b[i])prime[prime[0]++]=i;
		for(j=1;j<prime[0]&&i*prime[j]<MAXN;++j){
			b[i*prime[j]]=1;
			if(!(i%prime[j]))break;
		}
	}
	//printf("%d",prime[0]);
	--prime[0];
	scanf("%d%d",&L,&R);/*
	if(L>R){
		for(i=R;i<=L;i+=L-R){
			cout<<i<<endl;
			ans=1,x=i;
			for(j=1;prime[j]*prime[j]<=x;++j)
				if(!(x%prime[j])){
					tmpsum=1;
					while(!(x%prime[j])){
						x/=prime[j];
						++tmpsum;
					}
					ans*=tmpsum;
				}
			if(x-1)ans<<=1;
			if(ans>maxans){
				maxans=ans;
				maxi=i;
			}
		}
		printf("Between %d and %d, %d has a maximum of %d divisors.",L,R,maxi,maxans);
		return 0;
	}*/
	if(R-L>2500){
		x=upper_bound(a,a+tot,R)-a-1;
		while(x&&divsum[x]==divsum[x-1]&&a[x-1]>=L)--x;
		printf("Between %d and %d, %d has a maximum of %d divisors.",L,R,a[x],divsum[x]);
		return 0;
	}
	for(i=L;i<=R;++i){
		ans=1,x=i;
		for(j=1;j<prime[0]&&prime[j]*prime[j]<=x;++j)
			if(!(x%prime[j])){
				tmpsum=1;
				while(!(x%prime[j])){
					x/=prime[j];
					++tmpsum;
				}
				ans*=tmpsum;
			}
		if(x-1)ans<<=1;
		if(ans>maxans){
			maxans=ans;
			maxi=i;
		}
	}
	printf("Between %d and %d, %d has a maximum of %d divisors.",L,R,maxi,maxans);
}