题面

试题 D: 序列求和
本题总分:10 分
【问题描述】
学习了约数后,小明对于约数很好奇,他发现,给定一个正整数 t,总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣,并把它定义为$S_t$。
例如 $S_1 = 1$, $S_2 = 2$, $S_3 = 4$, $S_4 = 6$,· · · 。
现在小明想知道,前 60 个 $S_i$ 的和是多少?即 $S_1$ + $S_2$ + · · · + $S_{60}$ 是多少?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路

在网上找了半天都没有这题的正确题解,决赛A组的填空题都没人写题解?好吧,然而我也不会,写了个暴力,打表到50就不行了,看来答案至少到long long了。
请教了搞数学的队友yz @yingyingying002(yz tql),告诉我直接dfs搜索,分解数求值。

举个例子,求因子数为12的最小数。
在这里插入图片描述
$12 = 62;ans=2^53^1$
  $= 322;ans=2^23^15^1$
  $= 43;ans=2^33^2$
  $= 223;ans=2^23^15^1$

12有以上4种分解方法,每个乘数-1就是要求的数分解后的质数的幂次(唯一分解定理),接下来考虑如何分配这些幂次给质数使得数最小?显然贪心。我们看最后一种分解方法,12=2*2*3,将其降序排序,3,2,2,再减一为2,1,1,那么显然$2^23^15^1$能够让数尽量小并且满足因子数为12。

最后,我们dfs搜出所有的分解情况,然后其中最小的数。

另外,特判因子数为质数,比如因子数是13,减一是12,这个幂次全部分配给2,能得到的最小数是2^12^,满足因子数是13。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll N=1e5,inf=1e18;
bool vis[N+10];
ll prime[N+10],tot=0,mi;
void get_prime() // 素数筛
{
    memset(vis,1,sizeof(vis));
    vis[0]=vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[tot++]=i;
        for(int j=0;j<tot&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
ll qpow(ll a,ll b) // 快速幂
{
    ll s=1;
    while(b)
    {
        if(b&1)s=s*a;
        b/=2;
        a*=a;
    }
    return s;
}
ll dfs(ll x,vector<ll>g) // 将x分解成若干个数的乘积 
{
    if(vis[x]||x==1)return qpow(2,x-1); // 特判质数和1
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            ll t=x/i; // 大的那个数 
            g.push_back(i);

            // 更新mi 
            vector<ll>tmp=g;
            tmp.push_back(t); 
            sort(tmp.begin(),tmp.end(),greater<ll>());
            ll s=1;
            for(int j=0;j<tmp.size();j++)
                s*=qpow(prime[j],tmp[j]-1); 
            mi=min(mi,s);

            dfs(t,g);
            g.pop_back();
        }
    }
    return mi;
}
int main() 
{
    ios::sync_with_stdio(false);
    get_prime();
    ll ans=0;
    vector<ll>g;
    for(int i=1;i<=60;i++)
    {
        mi=inf;
        g.clear();
        ll ts=dfs(i,g);
        ans+=ts;
        //printf("i=%d ts=%lld ans=%lld\n",i,ts,ans);
    }
    printf("%lld\n",ans);
    return 0;
}

答案:292809912969717649