当前位置： 移动技术网 > IT编程>开发语言>C/C++ > nowcoder907B n的约数

nowcoder907B n的约数

2019年06月02日  | 移动技术网IT编程  | 我要评论

壁挂式空调,赵竞轩,我是猫咪不是虎

题意

t次询问，每次给你一个数n，求在[1,n]内约数个数最多的数的约数个数
\(t \le 500,n \le 10^{19}\)

思路

首先可以想到将n质因数分解。即\(n= \prod\limits_{i=1}^n{a_i}^{p^i}\)

答案就是\(\prod\limits_{i=1}^n{p_i+1}\)

然后我们要想办法让n最小，答案最大。

可以发现，如果存在\(a_i < a_j \&\& p_i < p_j\)，那么交换\(p_i,p_j\)一定会更优秀。

也就是说对于任意的\(a_i < a_j\)都有\(p_i \ge p_j\)

然后搜索即可

代码

/*
* @author: wxyww
* @date:   2019-05-31 19:26:20
* @last modified time: 2019-05-31 21:29:54
*/
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 100100;
#define int ll
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll dis[n],vis[n],js;
void eur() {
    int n = n - 100;
    for(int i = 2;i <= n;++i) {
        if(!vis[i]) dis[++js] = i;
        for(int j = 1;j <= js && 1ll * dis[j] * i <= n;++j) {
            vis[dis[j] * i] = 1;
            if(i % dis[j] == 0) break;
        }
    }
    return;
}
ll ans;
void solve(ll nans,ll now,ll x,ll lst) {
    for(int i = 1;i <= lst && x >= dis[now];++i)
        solve(nans * (i + 1),now + 1,x /= dis[now],i);
    ans = max(ans,nans);
}

signed main() {
    int t = read();
    eur();
    while(t--) {
        ll x = read();
        ans = 0;
        solve(1,1,x,10000);
        printf("%lld\n",ans);
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网