本文主要是介绍NOJ 1203 最多约数问题 (算数基本定理 DFS +剪枝),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最多约数问题
时间限制(普通/Java) : 20000 MS/ 30000 MS 运行内存限制 : 81920 KByte
题目描述
正整数x的约数是能整除x的正整数。正整数x的约数个数记为div(x)。例如,1,2,5,10都是正整数10的约数,且div(10)=4。 对于给定的2个正整数a<=b,编程计算a与b之间约数个数最多的数。
输入
输入的第1行有两个正整数a和b。
输出
若找到的a和b之间约数个数最多的数是x,则输出div(x)。
样例输入
1 36
样例输出
9
题目链接:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1203
题目分析:数论,算术基本定理的应用,加上各种牛逼的剪枝
本题的要求是,求出一个给定区间内的含约数最多的整数。
首先明确一下如何求一个数的约数个数:若一个数N满足:N = A1 N1 * A2 N2 * A3 N3 * …… * Am Nm,则n的约数个数为(N1 + 1) (N2 + 1) (N3 + 1) …… (Nm + 1)。这是可以用乘法原理证明的。
最浅显的算法是,枚举区间内的每个整数,统计它们的约数个数。这个算法很容易实现,但是时间复杂度却相当高。因为题目约定区间的最大宽度可以达到10^9的数量级,相当庞大。因此,在极限规模时,时间是无法忍受的。所以,我们需要尽量的优化时间。
分析一下枚举的过程就会发现,如果我们枚举到两个数n和m*n(m为一相对于n较大的质数),那么我们将重复计算n的约数两次。据此,我们发现了枚举效率低的根本所在。为了解决这一重复,我们可以选取另一种搜索方法——以质因子为对象进行深度搜索。
初始时,令number := 1,然后从最小的质数2开始枚举,枚举包含一个2、两个2……n个2的情况……直至number * 2 n大于区间的上限(max)。对于每种“2^k的情况”,令number := number * 2 n,再枚举3的情况,然后,枚举5的情况、7的情况……方法相同。整个过程是一个深度搜索的过程。当number大于等于区间下限(min)时,我们就找到了一个区间内的数,根据前面介绍的方法,可以得到它的约数个数。所有的区间内的数的约数个数的最大值就是我们要求的目标。
为什么这种深度搜索可以减少常规枚举过程中的重复问题呢?请看下面的一个例子
设给定的区间为[6,30],6,18,30为区间内的数,按照常规枚举方法,计算18,30,的时候分别计算了因子6的约数个数,重复计算2次。如果使用上述所说的深度搜索方法,求这3个数的因数个数的路径有一条公共部分,2*3,这一部分只计算了一次,求18只需再乘个3,求30只需再乘个5,相对于常规枚举减少了两次计算2*3的时间。但这种深度搜索也有问题,就是number有可能是无用的,下面的分析便是对这种深搜方法进行无用数据剪枝。
值得注意的是,我们枚举过程中得到的number可能无用的,即无论用number去乘以多少,都无法得到区间内的数。这样的number如果继续枚举下去,无疑会大大降低效率。那么,能否通过简单的判断,将其剪去呢?答案是可以的。很容易证明,如果(min – 1) div number < max div number,则区间内存在可以被number整除的数。因为,如果区间[min, max]内存在可以被number整除的数,也即是从min到max中至少有一个数能被number整除,那么区间[min – 1, max]内的数被number除得的商肯定不止一种,所以(min – 1) div number必然小于max div number。
反过来,如果(min-1)div number=max div number,则[min,max]内不存在可以被number整除的数。
证明如下:
假设[min,max]内存在可以被number整除的数
如果(min-1) div number=max div number,则min div number = max div number,那么①min等于max,且min和max均可以被number整除,或者②max>min,min可以被number整除,①的情况下可推出,(min-1) div nunber<max div number,与条件矛盾,舍去;②的情况下也可以推出(min-1) div number<max div number,舍去。所以结论成立。因此,我们只需枚举符合要求的number;至于不符合的,可以剪去。
此外,我们枚举的质数可能会达到很大。因为给出的整数最大可以达到4,000,000,000,它的质因数自然最大也可以到100,000,000的数量级。如果按上面的方法枚举,显然无法承受时间的压力。但是,我们又可以看到,对于区间内的任一整数,它包含的大于SQRT(4,000,000,000) = 2*31623的质因数最多只可能有一个。因此,我们只需枚举小于2*31623的质数。如果对一个符合要求的number(即,可以证明区间内至少存在一个数可以被number整除),无法找到一个小于2*31623的质数p使得number * p * x ∈ [min, max](x为一正整数)。那么,可知number需要乘以一个大于31623的质数才能得到number’,使得number’ ∈ [min, max]。根据前面介绍的乘法原理,只需将number包含的约数个数乘以2,即得number’包含的约数个数。
我们还能看到,如果当前搜索状态为(from, number, total),其中from是指当前枚举到的质因子(按从小到大枚举),total是指number中包含的约数个数。那么剩下的因子数最多为q = [log from(max / number)],这些因子组成的约数个数(即上述求约数个数时用到的一串乘积)最大为2 q。当前所能取到的(理想情况)最大约数个数就是total * 2 q,如果这个数仍然无法超过当前最优解,则这一分支可以剪去。
深度搜索的过程,从表面上看是一个指数级的复杂度。其实不然,更准确的说,复杂度应为O(p logn)。因为,它的指数增长速度是随n成对数级增长,本质上说,还是多项式级的算法。而且我们还进行了一些剪枝,由于枚举中的分支多数为非法的,因此通过剪枝可以去掉绝大多数的分支。这样就大大提高了程序的效率。
#include <cstdio>
#include <cstring>
#include <cmath>
int const MAX = 100005;
int prime[MAX];
int ma, cnt, l, r;void get_prime()
{bool get[MAX];memset(get, true, sizeof(get));get[0] = get[1] = false;for(int i = 2; i <= sqrt(MAX); i++)if (get[i])for(int j = i * i; j <= MAX; j += i)get[j] = false;for(int i = 2; i <= MAX; i++)if(get[i])prime[++cnt] = i;
}void search(int from, int tot, int num, int left, int right)
{ma = tot > ma ? tot : ma; if((left == right) && (left > num))search(from, tot * 2, num * left, 1, 1);for(int i = from; i <= cnt; i++) {if (prime[i] >right) return;else{int j = prime[i], x = left - 1, y = right, n = num, t = tot, m = 1;while(true){m ++; t += tot;x /= j;y /= j;if (x == y)break;n *= j;search(i + 1, t, n, x + 1, y);}if (tot < (ma / (1 << m)))return;}}
}int main()
{cnt = 0;get_prime();while(scanf("%d %d", &l, &r) != EOF){if((l == 1) && (r == 1))ma = 1;else{ma = 2;search(1, 1, 1, l, r);}printf("%d\n", ma);}
}
这篇关于NOJ 1203 最多约数问题 (算数基本定理 DFS +剪枝)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!