求不超过N的正整数中因子最多的数

本文主要是介绍求不超过N的正整数中因子最多的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述
Given an integer n, for all integers not larger than n, find the integer with the most divisors. If there is more than one integer with the same number of divisors, print the minimum one.

输入
One line with an integer n.
For 30% of the data, n ≤ 103
For 100% of the data, n ≤ 1016

输出
One line with an integer that is the answer.

样例输入
100
样例输出
60

我的程序：

#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;long prime[]={2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41};
ll result,n,maxDivisors;
void dfs(long t,ll now,ll divisors,ll lastNi){if(divisors > maxDivisors || (divisors==maxDivisors&&now<result)){maxDivisors = divisors;result = now;}int i = 1;while(now * pow(prime[t],i)<n && i<=lastNi){dfs(t+1,now * pow(prime[t],i),divisors*(i+1),i);i = i+1;}
}
int main()
{cin>>n;maxDivisors=0;dfs(0,1,1,100);cout<<result<<endl;return 0;
}

分析

题目大意
给定一个N，求不超过N的正整数中因子最多的数。如果有多个答案，输出最小的一个。

解题思路
本题是一道搜索题。

首先我们需要知道一个求因子个数的定理：

假设正整数n质因子分解为：

n = p1^n1 * p2^n2 * p3^n3 * ... * pk^nk

其中pi表示质因子，ni表示该质因子的数量，则有n的因子个数为：

D = (n1+1)*(n2+1)*(n3+1)* ... * (nk+1)

由此得到本题的一个基本解题思路：

枚举质因子数量，在使得n不超过N的情况下，使得D尽可能大

为了要D尽可能大，需要ni尽可能大，所以pi要尽可能小。

因此我们从最小的质数2开始枚举每一个质因子的数量ni，来计算n。

DFS(prime, now, divisors):If (prime > n) ThenReturn ;End IfIf (divisors > maxDivisors or(divisors == maxDivisors && now < result)) ThenmaxDivisors = divisorsresult = nowEnd Ifi = 0While (now * prime^i <= n) ThenDFS(next_prime, now*prime^i,divisors*(i+1))i = i + 1End While

上面这段代码是可以计算出正确结果的，但是会严重的超时。因此我们还需要其他的剪枝，这里利用一个性质：

对最小解来说一定有：若pi和pj都属于n的质因子，且pi < pj，则一定有ni≥nj，其证明如下：

假设存在nj > ni，则有：。

n' = n / pj^(nj-ni) * pi(nj-ni)

n’的质因子个数和n相比，只是交换了ni和nj的值，因此D的值不会发生变化。而由于pj > pi，因此 n’ < n，所以 n 不是最小解。

同时由这个性质，我们可以知道当pi存在于n的质因子分解时(即ni≥1)，所有比pi小的质数一定也存在于n的质因子分解中。

所以我们推断出最大可能出现的质数为41，因为2~41之间的质数相乘刚好是小于10^16 ，若再乘上43，就会超过10^16。

由此得到改进后的搜索函数：

DFS(prime, now, divisors, lastNi):If (divisors > maxDivisors or(divisors == maxDivisors && now < result)) ThenmaxDivisors = divisorsresult = nowEnd Ifi = 1   // 由于使用了当前质数才能使用后面的质数，因此这个质数至少要使用1次While (now * prime^i < n && i <= lastNi) Then// 确保i小于等于上一个质数的数量DFS(next_prime, now*prime^i,divisors*(i+1), i)i = i + 1End While