牛客 n的约数(唯一分解定理)

题面：https://www.cnblogs.com/wangtao971115/p/10358229.html

题面

$t$次询问，每次给你一个数$n$，求在$[1,n]$内约数个数最多的数的约数个数

解法

求一个数的约数个数有一个唯一分解定理:
素因子分解
求n的约数个数:
$n=p1^k1\times p2^k2\times ……\times pn^kn$,其中$p_1,p_2,……,p_n$为互不相同的质数,$k_1,k_2,……,k_n$为正整数（这叫$n$的标准分解）
则$n$所有正约数个数为$(k1+1)(k2+2)……(kn+1)$个
$60=3^1\times 2^2\times 5^1$
约数个数$=(1+1)\times (1+1)\times (2+1)=12$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1 << 15;
ll ans, n;
ll prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
void dfs(int pos, int now, ll val, ll cnt)
{
	//pos为素数下标,cnt是低位对高位素数的限制,val为目前因子的个数
    if(pos > 15)
        return;
    ans = max(ans, val);
    for(int i = 1; i <= cnt; i++)
    {
        if(n / prime[pos] < now)
            break;
        now *= prime[pos];
        dfs(pos + 1, now, val * (i + 1), i);
    }
}
int main()
{
    int cas; cin >> cas;
    while(cas--){
        cin >> n;
        ans = 0;
        dfs(1, 1, 1, 64);
        cout << ans << endl;
    }
    
    return 0;
}