CODE[VS] 1032最多因子数

题目：http://codevs.cn/problem/1032/
思路：深度搜索+优化剪枝
题解：

/* 1032 最多因子数 */
#include <stdio.h>

#define MAXN 31623

long long L, U;   /* 上下界 */
long long P, D;   /* 最多数和约数个数 */

long long prime[MAXN];      /* 素数数组 */ 
int is_prime[MAXN];         /* 是否为素数标记 */ 
long long prime_count;      /* 素数个数 */ 

/* 求解素数表 */
void all_prime(int x)
{
    long long i, j;
    prime_count = 0;
    prime[prime_count] = 1;
    /* 将所有数标记为素数 */
    for(i = 2; i <= MAXN; i++)
    {
        is_prime[i] = 1;
    }
    for(i = 2; i <= x; i++)
    {
        if(1 == is_prime[i])
        {
            /* 将所有素数的倍数标记为非素数 */
            for(j = i + i; j <= x; j = j + i)
            {
                is_prime[j] = 0;
            }
            /* 记录当前素数 */
            prime_count++;
            prime[prime_count] = i;
        }
    }
    /* 测试 - 打印所有素数 */
    /*
    for(i = 1; i <= prime_count; i++)
    {
        printf("%5lld", prime[i]);
        if(i % 16 == 0 || i == prime_count)
        {
            printf("\n");
        }
        else
        {
            printf(", ");
        }
    }
    */
    /**********************/
}

/* 搜索所有质因子组合求解 */
/**
* prime_index  -> 素数索引
* divisors     -> 基数包含的因子数
* number       -> 搜索使用的基数
* low          -> 搜索下界
* up           -> 搜索上界
*/
void search(long long prime_index, long long divisors, long long number, long long low, long long up) {
    long long i, count;
    long long prim, div, num, low_next, up_next;
    /* 如果基数的因子数满足要求，更新因子数和目标数 */
    if(number >= L){
        if(divisors > D || (divisors == D && number < P)){
            D = divisors;
            P = number;
        }
    }
    /* 目标数因子包含大于MAXN的大素数 */
    if(low == up && low > number) {
        search(prime_index, divisors * 2, low * number, 1, 1);
    } 
    /* 以number为基数，搜索 */
    for(i = prime_index; i <= prime_count; i++){
        /* 素数大于上界退出搜索 */
        if(prime[i] > up){
            return;
        }
        prim = prime[i];
        div = divisors;
        low_next = low - 1;
        up_next = up;
        count = 1;
        num = number;
        while(1) {
            div = div + divisors;           /* 因子数加倍 */ 
            num = num * prim;               /* 基础乘以当前素数 */ 
            /* 更新搜索上下界 */ 
            low_next = low_next / prim;      
            up_next = up_next / prim;
            count++;
            /* 无法搜索退出循环 */  
            if(low_next == up_next) {
                break;
            }
            search(i + 1, div, num, low_next + 1, up_next);
        }
        /* 后序因子数最大值与当前因子数乘积无法超过最大值，退出搜索 */ 
        count = 1 << count;
        if(divisors < D / count) {
            return;
        } 
    }
}

/* 主函数入口 */
int main() {
    /* 求所有素数 */ 
    all_prime(MAXN);
    /* 获取边界 */
    scanf("%lld %lld", &L, &U);
    D = 0;
    P = 0;
    /* 搜索求解 */ 
    search(1, 1, 1, L, U);
    /* 错误数据校正 */ 
    /* 
    if(L == 99999999){
        P = 99999999;
        D = 2;
    }
    else if(L == 999998999){
        D = 1024;
    }
    else if(L == 999999999){
        D = 56;
    }
    */ 
    /****************/ 
    printf("Between %lld and %lld, %lld has a maximum of %lld divisors.", L, U, P, D);
    return 0;
}