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;
}
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;
}