Mathematicians love all sorts of odd properties of numbers. For instance, they consider 945 to be aninteresting number, since it is the first odd number for which the sum of its divisors is larger than thenumber itself.To help them search for interesting numbers, you are to write a program that scans a range ofnumbers and determines the number that has the largest number of divisors in the range. Unfortunately,the size of the numbers, and the size of the range is such that a too simple-minded approach may taketoo much time to run. So make sure that your algorithm is clever enough to cope with the largestpossible range in just a few seconds.
Input
The first line of input specifies the number N of ranges, and each of the N following lines contains arange, consisting of a lower bound L and an upper bound U, where L and U are included in the range.L and U are chosen such that 1 ≤ L ≤ U ≤ 1000000000 and 0 ≤ U − L ≤ 10000.
Output
For each range, find the number P which has the largest number of divisors (if several numbers tie forfirst place, select the lowest), and the number of positive divisors D of P (where P is included as adivisor). Print the text ‘Between L and H, P has a maximum of D divisors.’, where L, H, P,and D are the numbers as defined above.
Sample Input
31 101000 1000999999900 1000000000
Sample Output
Between 1 and 10, 6 has a maximum of 4 divisors.Between 1000 and 1000, 1000 has a maximum of 16 divisors.Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
分解质因数~
题意为求[L,R]中哪个数的因数最多。
因为因子数不要求去重，所以对于每一个数的所有因子来说，有选一个，选两个，…，全选这k+1种选法，其中k是这个数中这个因子的个数，预处理出所有质数，然后依次将区间内的每个数分解，更新maxx值即可。
#include<cstdio> #include<cstring> int t,le,ri,maxx,num,a[40001],k; bool b[40001]; void findd() { for(int i=2;i<40000;i++) { if(!b[i]) a[++a[0]]=i; for(int j=1;a[j]*i<40000;j++) { b[a[j]*i]=1; if(!(i%a[j])) break; } } } int cal(int u) { int ans=1; for(int i=1;a[i]*a[i]<=u;i++) if(!(u%a[i])) { int tot=1; while(!(u%a[i])) tot++,u/=a[i]; ans*=tot; } if(u>1) ans*=2; return ans; } int main() { findd(); scanf("%d",&t); while(t--) { scanf("%d%d",&le,&ri);maxx=0; for(int i=le;i<=ri;i++) if((k=cal(i))>maxx) { maxx=k;num=i; } printf("Between %d and %d, %d has a maximum of %d divisors.\n",le,ri,num,maxx); } return 0; }
