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

2012-09-04 14:20:46| 人氣570| 回應0 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

给你一个范围的数，请你写一个程式找出在这个范围内的数，哪一个数有最多的除数（就是小于等于这个数，且可以被这个数除尽的数。例如：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;
}

我要檢舉

#d717#好多因子

台長： Morris

您可能對以下文章有興趣

d985. Gran Turismo 5

[ZJ] a473. 外援計畫

d618. 有限狀態自動機（Finite State Machine）

d825. 隔熱紙

人氣(570) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][建表非DP] a532. 奇特的數列
此分類上一篇:[ZJ][二分Greedy] d830. 暗門2

回應(0)