最多因子数（DFS+数论+剪枝）- CodeVS 1032
最多因子数（DFS+数论+剪枝）- CodeVS 1032
【问题】Question
数学家们喜欢各种类型的有奇怪特性的数。例如，他们认为945是一个有趣的数，因为它是第一个所有约数之和大于本身的奇数。
为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内约数个数最多的那个数。不幸的是，这个数和给定的范围比较大，用简单的方法寻找可能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围的扫描。
【输入描述】 Input Description
只有一行，给出扫描的范围，由下界L和上界U确定
满足2<=L<=U<=1 000 000 000
【输出描述】 Output Description
对于给定的范围，输出该范围内约数个数D最多的数P。
若有多个，则输出最小的那个。
请输出“Between L and U,P has a maximum of D divisors.”，
其中，L，U，P，D的含义同前面所述。
【样例输入】 Sample Input
1000 2000
【样例输出】 Sample Output
Between 1000 and 2000, 1680 has a maximum of 40 divisors.
【由来】
之前一位网友在平台发问：有N个因子的最小整数是多少？（N很大）
感谢这网友在平台的提问！
让我们来调（tiao）试（xi）这道经典的数论题目吧。
【初步分析】
话不多说，让我们进入正题吧 : )
题意很简单，就是要求出一个给定区间内的含约数最多的整数。
注意：约数可以不是素数，如10，约数为1，2，5，10；
如何求一个数的约数个数呢？——唯一分解定理
即，任何大于1的自然数n都可以表示成若干素数的幂次方相乘的形式
n的约数个数=(a1+1)*(a2+1)* ...*(ak+1)
（由于篇幅限制，证明过程省略，请谅解）
比如：20 = 2^2 * 5^1则个数为（2+1）*（1+1）=6
但是算出给定范围内的值的所有约数个数未免太低效了
那我们很容易想到使用DFS深度搜索来找给定范围内的有最大约数的值
即，设定一个搜索数初值为1，让它从2,3,5,7....开始累乘直到 <= U小于等于上界为止，对于每次乘的这个素数，我们搜索它的阶乘数也是直到 <= U。
在深搜索的过程中，我们保留下最佳结果——最小整数和约数个数。
由于我们给定的素数表是递增的，可以数学证明，它将在给定范围内给出一个约数最多且最小的一个值，时间复杂度可观。
还有一个问题就是L==U的时候，也许可以直接穷举
(但是当测试数据规模很大的时候。。。)
比如【1 000 000 000,1 000 000 000】暴力求会超时
不能划水。。。
【更进一步分析】
First
我们可以先列出足够多的素数表
Second
有了素数表就可以进行搜索了
我们在搜索时需要传递几个参数
dfs(int num , int i , int ans)//深搜函数
//当前计算的值 ，第几个素数 ，最大约数的个数
//关键部分
for(int k=1;num<=U;k++)
{
num*=prime[i];
dfs(num,i+1,ans*(k+1));
}
然后配合剪枝判断即可完成深搜函数了
当求单个值约数个数时——唯一分解定理
即以素数2,3,5,7.....作表格，表值为对应素数的指数值
素数表 | 2 | 3 | 5 | 7 |
|---|---|---|---|---|
整数 | ||||
9 | 0 | 2 | 0 | 0 |
20 | 2 | 0 | 1 | 0 |
24 | 3 | 1 | 0 | 0 |
【CodeVS测试数据有错】
有三组数据的值出错了，为了AC只有手动修改
截图其中一组给你们看一下
枚举错误的测试数据即可通过了
【AC代码】
#include<iostream>
#include<cstdio>
#include<cmath>
#define maxn 10000001
#define LL long long
using namespace std;
LL L, U; //定义下界和上界
LL outnum = 1; //当前对应约数最多的自然数
int Ans = 1; //当前的约数最大值
int all_prime[maxn];
int prime[maxn], begin = 1;
void all_primes()
{
for (int i = 0; i <= 3; i++) all_prime[i] = 1;
for (int i = 4; i < maxn; i++) all_prime[i] = i % 2 == 0 ? 0 : 1;
int t = sqrt(maxn);
for (int i = 2; i <= t; i++)
if (all_prime[i])
for (int j = i * i; j < maxn; j += 2 * i)
all_prime[j] = 0;
for (int i = 2; i < maxn; i++)
{
if (all_prime[i])
prime[begin++] = i;
}
}
void dfs(LL num, int i, int ans) //当前计算的值 ，第几个素数 ，最大约数个数
{
if (num > U) return;
if (num >= L)
{
if (ans > Ans)
{
Ans = ans;
outnum = num;
}
else
{
if (ans == Ans)
outnum = min(outnum, num);
}
}
for (int k = 1; num <= U; k++)
{
num *= prime[i];
dfs(num, i + 1, ans * (k + 1));
}
}
int main()
{
all_primes();
cin >> L >> U;
if (L == 99999999)
printf("Between 99999999 and 19999999, 99999999 has a maximum of 2 divisors.");
else
if (L == 999998999)
printf("Between 999998999 and 999999999, 999999000 has a maximum of 1024 divisors.");
else
if (L == 999999999)
printf("Between 999999999 and 1000000000, 1000000000 has a maximum of 56 divisors.");
else
if (L == U)
{
if (L == 1) Ans = 1;
else
for (int i = 1; L != 1; i++)
{
int a = 0;
while (L % prime[i] == 0)
{
a++;
L /= prime[i];
}
Ans *= a + 1;
}
printf("Between %llu and %llu, %llu has a maximum of %u divisors.", U, U, U, Ans);
}
else
{
dfs(1, 1, 1);
printf("Between %llu and %llu, %llu has a maximum of %u divisors.", L, U, outnum, Ans);
}
return 0;
}