脚本宝典收集整理的这篇文章主要介绍了【YBTOJ】【DFS】最多约数，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

最多约数

给定一个正整数 (n) ，对于所有不超过 (n) 的正整数，找到包含约数最多的一个数。如果有多个这样的数，那么回答最小的那个。

(nleq 10^{16})

题解

首先有一个结论：

• 若正整数 (N) 被唯一质因数分解为 (N=p_1^{c_1}p_2^{c_2}dots p_m^{c_m}) ，且满足 (p_1<p_2<dots<p_m) ，
• 则： (N) 的正约数个数为 (PRodlimITs_{i=1}^m (c_i+1)) .

应用这个结论，我们可以直接枚举因数的 (i) 次方，进行搜索优化。

另外有一个剪枝：

• 题目要求数最小，则可知满足时， (c_1ge c_2gecdots c_m) 必定成立。
• 则 (i) 加上限制即可。

代码

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define fo(a) freoPEn(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e6+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9'))ch=c,c=getchar();
	while(c>='0'&amp;&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
ll n,m;
ll pri[N]; bool vis[N];
void Prime(){
	for(int i = 2 ; i <= 1e6 ; i ++){
		if(!vis[i]) pri[++m] = i;
		for(int j = 1 ; j <= m && i*pri[j] <= 1e6 ; j ++){
			vis[i*pri[j]] = 1;
			if(!(i%pri[j])) break;
		}
	}
}
ll anS,anC;
void DFs(int cur,int lim,ll s,ll c){
	if(c > anC || (c == anC && s < anS)) anS = s , anC = c;
	if(cur > m || s * pri[cur] > n) return;
	s *= pri[cur];
	for(int i = 1 ; i <= lim && s <= n ; i ++ , s *= pri[cur])
		dfs(cur+1,i,s,c*(i+1));
}
signed main(){
	n = read();
	Prime();
	dfs(1,53,1,1);
	printf("%lld",anS);
} 

脚本宝典总结

以上是脚本宝典为你收集整理的【YBTOJ】【DFS】最多约数全部内容，希望文章能够帮你解决【YBTOJ】【DFS】最多约数所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。