2012-09-04 14:20:46Morris

[ZJ][dfs搜索+剪枝優化] d717. 好多因子

內容 :

给你一个范围的数,请你写一个程式找出在这个范围内的数,哪一个数有最多的除数(就是小于等于这个数,且可以被这个数除尽的数。例如:6有4个除数,分别是1,2,3,6)。数的大小超大,范围也超大,所以你的程式必须有效率,否则可能无法在几秒内跑完。

輸入說明 :

输入的第一列有一个正整数N,代表以下有几组 测试资料。每组测试资料一列,含有2个正整数L,U,代表某一范围的数中最小及最大的数。并且1 <= L <= U <= 2147483647,0 <= U-L <= 2147483646.

輸出說明 :

对每一组测试资料,找出在范围内有最多除数的数P(如果有不止一个数有最多除数,请找最小的那个),以及他有多少个除数D。然后依这样的格式输出:'Between L and U , P has a maximum of D divisors.。请参考Sample Output。

範例輸入 :

4
1 10
1000 1000
999999900 1000000000
1 2147483647

範例輸出 :

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.
Between 1 and 2147483647, 2095133040 has a maximum of 1600 divisors.

提示 :

ACM 294 d366: Divisors 加强版

再想想别的什么更快的方法!d366中的提示在这题是应该有用的,但不稍加改进就会TLE哟!

大概不超过100笔测资,测资有误或太简单欢迎提供及修正...

出處 :

ACM 294 d366: Divisors 加强版 (管理:liouzhou_101)

1. 當 U - L 小的時候, 直接遍歷搜索即可, 以下程式碼先暫定 10,0000 為界線,
2. 當 U - L 大的時候, 我們開始窮舉該數字的質因數, 從小到大開始窮舉,
    2 有 0, 1, 2, ... 3 有 0, 1, 2, ... 類推, 剪枝的條件,
    我們先假設搜索狀態 (pi, num, tot) 當前質因數 pi, 當前枚舉數字 num, num 所擁有的因數個數,
    剩餘最多因數估計 q = [log (U/num) / log(pi)], 能湊成的個數即是 pow(2, q),
    如果 tot * pow(2, q) < 目前最多個數的因數時, 則回傳。
    此外當 (L-1)/num == U/num 時, 即是無法達到該區間內, 就可以回傳了
    為了加速 dfs 的剪枝, 我們可以預先找倒數 500 個數字的最多因數個數, 好讓 dfs 在此之前快速剪枝。


#include <stdio.h>
#include <math.h>
int L, U;
int p[5200], pt = -1;
long long p2[50] = {1};
void sieve() {
    int i, j, mark[50005] = {};
    for(i = 2; i <= 50000; i++) {
        if(!mark[i]) {
            for(j = i+i; j <= 50000; j += i)
                mark[j] = 1;
            p[++pt] = i;
        }
    }
}
int ans, ans_num;
void dfs(int idx, long long num, int tot) {
    if(U/num == (L-1)/num)  return;
    if(tot > ans || (ans == tot && num < ans_num)) {
        ans_num = num;
        ans = tot;
    }
    int i, q;
    long long j;
    if(idx > pt)  return;
    q = log((double)U/num)/log(p[idx]);
    if(tot*p2[q] < ans || (tot*p2[q] == ans && num >= ans_num))  return;
    for(i = 0, j = 1; num*j <= U; i++, j *= p[idx]) {
        dfs(idx+1, num*j, tot*(i+1));
    }
}
int main() {
    sieve();
    int t;
    long long i, j;
    for(i = 1; i < 50; i++)
        p2[i] = p2[i-1]<<1;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &L, &U);
        if(U-L > 100000) {
            ans = 0;
            for(i = U-500; i <= U; i++) {
                int n = i, cnt = 0, tans = 1;
                for(j = 0; j <= pt && (long long)p[j]*p[j] <= n; j++) {
                    if(n%p[j] == 0) {
                        cnt = 0;
                        while(n%p[j] == 0)
                            cnt++, n /= p[j];
                        tans *= cnt+1;
                    }
                }
                if(n != 1)  tans *= 2;
                if(tans > ans)
                    ans = tans, ans_num = i;
            }
            dfs(0, 1, 1);
        } else {
            ans = 0;
            for(i = L; i <= U; i++) {
                int n = i, cnt = 0, tans = 1;
                for(j = 0; j <= pt && (long long)p[j]*p[j] <= n; j++) {
                    if(n%p[j] == 0) {
                        cnt = 0;
                        while(n%p[j] == 0)
                            cnt++, n /= p[j];
                        tans *= cnt+1;
                    }
                }
                if(n != 1)  tans *= 2;
                if(tans > ans)
                    ans = tans, ans_num = i;
            }
        }
        printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, ans_num, ans);
    }
    return 0;
}