题解 P1221 【最多因子数】

Wenxiang_MCL · 2017-09-14 21:24:22 · 题解

首先，这是一道暴搜题，主要是考对因数个数性质的了解；

首先介绍一个公式每一个整数n都可以由质数相乘得到

可得n = a1 ^ t1 * a2 ^ t2 * a3 ^ t3 .... an ^ tn,则n因子的个数则为(t1 + 1) * (t2 + 1) * (t3 + 1) ... *(tn + 1);

其中a1 --- an 为质数;

得到这个公式后，便可以开始暴搜

唯一的算得上剪枝的地方就是在枚举时递增枚举；

下面上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int factor[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,87,91,97};//100以内的素数表
int divi[30];//存储指数t
long long int up,down,ans,cnt;
void dfs(long long int num,int sta);
void ccount(long long int num);
void ccount(long long int num){
    long long int cnum = 1;
    for(int i = 1;i <= 26;i ++){
        cnum *= (divi[i] + 1);
    }
    if(cnum > cnt) cnt = cnum,ans = num;
    if(cnum == cnt) ans = min(num,ans);

}//计算质因子个数

void dfs(long long int num,int sta//sta防止重复){
    if(num > up) return;
    if(num <= up && num >= down){//满足条件，计算
        ccount(num);
    }
    for(int i = sta;i <= 26;i ++){//枚举所有质因子
        divi[i] ++;
        dfs(num * factor[i],i);
        divi[i] --;
    }
}
int main (){
    scanf("%lld%lld",&down,&up);
    if(down == up && up == 131074){//小小的特判，因为这个数好像撞到了100以上的质数，如果想过的话可以求出更大的质数
        ans = 131074,cnt = 4;
        printf("Between %lld and %lld, %lld has a maximum of %lld divisors.",down,up,ans,cnt);
        return 0;
    }
    dfs(1,1);
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.",down,up,ans,cnt);
    return 0;
}