自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 23:07:09，当前版本为作者最后更新于2025-01-02 07:36:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

新年第一题。

首先考虑如何算 $f(n)$。设 $n=\prod_i p_i^{k_i}$，可以发现 $f(n)$ 只与 $k_i$ 有关。但是还是难以计算 $f(n)$，此时我们需要一个结论：

令 $\Omega(n)$ 为 $n$ 的质因数分解中的 $k_i$ 之和。则一定存在一种最优解使得任意两个被选中的数 $a,b$ 都满足 $\Omega(a)=\Omega(b)$。

这个结论我还不会证，可能以后会补充完整。

猜出这种构造并不难，因为看起来这种构造就是很优的，且显然有合法性和极大性。

这样我们只需要做背包就能计算 $f(n)$ 了。但是要求的是 $f$ 的前缀和，把 $0$ 去掉后直觉上本质不同的 $\{k_i\}$ 应该是很少的，搜出来一共只有大约 $2.3\times 10^4$ 种，容易对于每种 $\{k_i\}$ 求出其对应的 $f(n)$。

现在我们只需要算出有多少个 $n$ 质因子次数是 $\{k_i\}$ 即可。直接爆搜除了最后一位以外的位置填哪些质数，最后一位次数如果是 $1$ 则可以使用 Min_25 筛做质数前缀统计，否则能填的最大质数不到 $\sqrt n$ 可以线性筛时直接预处理。可以发现这个东西跑的飞快然后就过了。

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <cmath>

#define rgall(arr) (arr).begin(),(arr).end()
#define rgcnt(arr,cnt) (arr).begin(),(arr).begin()+(cnt)
#define rgo1(arr,cnt) (arr).begin()+1,(arr).begin()+1+(cnt)
#define rgany(arr,cnt,offset) (arr).begin()+(offset),(arr).begin()+(offset)+(cnt)

using namespace std;

array<long long,800000> dpp0,bpos;
const array<int,15>     DFSps={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
array<int,400000>       primes,sump0;
bitset<400000>          isprime;
vector<int>             cntps,sumps;
long long               answer,cntp,n,n2;
int                     divline;

long long fast_pow(long long base,long long exp)
{
    long long result;
    for(result=1;exp;exp&1?result=result*base:true,base=base*base,exp>>=1);
    return result;
}
inline long long xrooti(long long a,int b)
{
    return pow(a,1./b)+1e-10;
}
inline int loc_idx(long long a)
{
    return a>n2?n/a:n2-a+divline;
}
long long DFS_count(int dep,long long a,int pidx)
{
    if(cntps.empty())
        return 1;
    if(dep==cntps.size()-1)
    {
        if(cntps.back()==1)
            return max(0ll,dpp0[loc_idx(a)]-pidx);
        return max(sump0[xrooti(a,cntps.back())]-pidx,0);
    }
    long long result=0;
    for(int i=pidx+1;i<=cntp&&fast_pow(primes[i],sumps[dep])<a;i++)
        result+=DFS_count(dep+1,a/fast_pow(primes[i],cntps[dep]),i);
    return result;
}
void DFS_factor(int dep,long long a,const long long n)
{
    array<int,60> dp{1};
    for(int i:cntps)
        for(int j=59;j;j--)
            for(int k=1;k<=i&&k<=j;k++)
                dp[j]+=dp[j-k];
    int maxc=0;
    for(int i:dp)
        maxc=max(maxc,i);
    sumps=cntps;
    for(int i=(int)cntps.size()-2;i>=0;i--)
        sumps[i]+=sumps[i+1];
    answer+=maxc*DFS_count(0,n,0);
    cntps.push_back(1);
    a=a*DFSps[dep];
    while(a<=n)
    {
        DFS_factor(dep+1,a,n);
        a=a*DFSps[dep],++cntps.back();
    }
    cntps.pop_back();
}

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n,n2=sqrt(n)+1e-9;
    for(int i=2;i<=n2;i++)
    {
        sump0[i]=sump0[i-1];
        if(!isprime[i])
            primes[++cntp]=i,++sump0[i];
        for(int j=1;j<=cntp&&i*primes[j]<=n2;j++)
        {
            isprime.set(i*primes[j]);
            if(!(i%primes[j]))
                break;
        }
    }
    int cntb=0;
    for(long long i=1,j;i<=n;i=n/j+1)
    {
        ++cntb,dpp0[cntb]=(j=bpos[cntb]=n/i)-1;
        if(!divline&&j<=n2)
            divline=cntb;
    }
    for(int i=1;i<=cntp;i++)
        for(int j=1;1ll*primes[i]*primes[i]<=bpos[j];j++)
            dpp0[j]-=dpp0[loc_idx(bpos[j]/primes[i])]-i+1;
    DFS_factor(0,1,n);
    cout<<answer;
    return 0;
}