题解 P1221 【最多因子数】

· · 题解

题意：

给定范围 l 与 r ，求在 [l,r] 这一段区间里因子个数最多的数以及它的因子个数。

思路：

因为 l 和 r 都到了 10^9 级别，所以一个个枚举过去肯定不行，这时候小奥就起了很大的帮助。

我们都知道，若一个数为 a[1] ^{p[1]}*a[2]^{p[2]}*...*a[n]^{p[n]} ，那么它的因子个数就为\prod_{i=1}^n{p[i]+1}

所以我们可以枚举质数以及每个质数的指数，如果相乘大于等于 l 且小于等于 r，那么就比较答案，若因子个数比答案大或者与答案相等但是数比答案小，那么就更新答案，最后输出即可。

2*3*5*7*11*13*17*19*23*29>10^9

注意：

因为有些数据可能涉及到了 100 以外的质数，大家可以打一张质数的表来解决。

Code: 
#include<bits/stdc++.h>
#define N 1000000000
using namespace std;
int a[10005];
int l,r,tot;
bool flag[100005];
long long temp,ans,anss,sum;
void Solve(int x,long long s,long long ans){
    temp=s;
    if(s>=l&&s<=r){
        if(ans>sum){sum=ans;anss=s;}
        else if(sum==ans&&s<anss)anss=s;
    }
    if(x==tot+1)return;
    if(s*a[x]>r)return;
    int num=0;
    while(temp*a[x]<=r){
        temp=temp*a[x];
        num++;
        Solve(x+1,temp,ans*(num+1));
    }
    Solve(x+1,s,ans);
}
void Init(){
    memset(flag,false,sizeof(flag)); 
    for(int i=2;i<=sqrt(N);i++)
        if(flag[i]==false){
            a[++tot]=i;
            for(int j=2;j<=sqrt(N)/i;j++)
                flag[i*j]=true; 
        }
}
int main(){
    Init();
    scanf("%d%d",&l,&r);
    Solve(1,1,1);
    printf("Between %d and %d, %lld has a maximum of %lld divisors.\n",l,r,anss,sum);
    return 0;
}