dfs应用

题目:牛客网想开了第二题
首先求一个数约数的个数的公式
举个例子
12=2²x3¹ 那12的约数的个数就是（2+1）（1+1）个
所以这道题的思路就是求他的n以内中最大的数的因数的的指数的乘积的最大值，如果用暴力的话肯定会超时，而一般情况下越大的范围一般就他的约数的个数就越多。
根据唯一分解定理，ans=p1^e1xp2^e2……pk^ek,pi为素数且p1=e2>=…>=ek，(贪心)即后一个素数的幂肯定小于等于前一个素数的幂，这里就用dfs来搜索他的个数。
他的数据给的是10⁹所以不用太多的因数，15个足够。
code:

#include<iostream>
using namespace std;

typedef long long ll;

ll res[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

ll total=0;
ll number;

void dfs(ll k,int lim,ll num,ll cnt){
    if(k>14) return;
    total=max(total,cnt);
	int i=1;
	for(i;i<=lim;i++){
		if(num<=number/res[k]){
			num*=res[k];
			dfs(k+1,i,num,cnt*(i+1));
		}else break;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	int i=0;
	for(i;i<t;i++){
		cin>>number;
		total=1;
		dfs(0,15,1,1);
		cout<<total<<endl;
	}
	return 0;
}

注意：这里用的是num<=number/res[k] 主要是防止ll爆掉如果用res[k]num<=number，long long 可能就爆了。