自动搬运

查看原文

来自洛谷，原作者为

	动物世界 **

搬运于2025-08-24 22:05:05，当前版本为作者最后更新于2018-10-09 18:08:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

%%%……这道题蒟蒻想了好久啊…

写个题解纪念下，同时也为和我一样看不懂出题人题解的oier们指点一条新的道路

肯定还是要先预处理出每个数质因数的个数，这个用线性筛可以解决，因为它是一个“和性函数”。此外，还要预处理出斐波那契数列，大概40个吧。

我们可以建立一个数组$a$，如果这个数$x$还没有被选过，$a[x]$就为$1$，反之$a[x]$则为$0$,建立一个树状数组$c$记$a$的前缀和。

假设$Ni$是$maxn$，$num[w][j]$表示第$w$行第$j$个编号为多少，$sum[w][j]$表示第$w$行前$j$个数的质因数个数的前缀和，那么询问的时候答案就是$sum[ki][r]$，$r$就是在$num[w]$中小于等于$Ni$的最大值的下标。（即$upper\_bound(Ni)-1$）

那么$sum$怎么预处理呢？

我们可以知道，第$w$行的第$1$个数即为选完$w-1$行后剩下来的第$1$个数，第$2$个即为选完$w-1$行后剩下来的第$2$个数，第$j$个即为剩下来的第$j$个预处理出的斐波那契数。而处理完第$j-1$个数之后，那个位置上的$a[x]$会变成$0$，那我们要找到第$j$个数是什么，只要找到一个$p$，使得$p$在$a$的前缀和恰好等于$fib[j]-j+1$即可（这里理解一下啊），然后我们就可以预处理出$sum$以及$num$数组了。

但是问题又来了：怎么找呢？

笔者一开始想到的是$\log^2{n}$的树状数组+二分，但是感觉会T，于是冥思苦想+学习了树状数组加倍增的精妙写法……主要代码在下面，相信学过倍增和树状数组的oier们都能看懂…

int t=(1<<22),pos=0;
    int tot=0;
    for(;t;t>>=1){
    	if(tot+c[t+pos]<x){
    		pos+=t;
    		tot+=c[pos];
		} 
	}
    return pos+1;

这是一种非常实用的方法，在许多题目里都可以用来减少一个$\log{n}$的复杂度

大家一定都明白了吧！

时间复杂度：$O(n\log{n}+T\log{n})$

最后吐槽一点，按照我随性的代码风格，卡空间这种操作令我痛不欲生啊……

下面是完整代码（部分变量名可能与题解里的不同，大家看懂就好）

#include<bits/stdc++.h>
using namespace std;
template<typename T>void Read(T &x){
    x=0;int f=1;char s=getchar();
    while(!isdigit(s)){if(s=='-') f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}
const int maxn=5*1e6,maxk=1e4,fbnq_size=45;
int c[maxn+10],p[100];
inline int lowbit(int x){
    return x&-x;
}
void add(int x,int y){
    for(;x<=maxn;x+=lowbit(x)) c[x]+=y;
}
int pri[maxn/10];
bitset<maxn+10> fac;
short d[maxn+10];
int siz=0;
void do_d(){
    for(int i=2;i<=maxn;i++){
        if(fac[i]==0){
            pri[++siz]=i;
            d[i]=1;
        }
        for(int j=1;j<=siz;j++){
            if(i*pri[j]>maxn) break;
            fac[i*pri[j]]=1;
            d[i*pri[j]]=d[i]+1;
            if(i%pri[j]==0) break;
        }
    }
}
vector<int> sum[maxk+10];
vector<int> num[maxk+10];
int find_num(int x){
    int t=(1<<22),pos=0;
    int tot=0;
    for(;t;t>>=1){
    	if(tot+c[t+pos]<x){
    		pos+=t;
    		tot+=c[pos];
		} 
	}
    return pos+1;
}
void pre_process(){
    do_d();
    p[1]=1;p[2]=2;
    for(int i=3;i<=fbnq_size;i++) p[i]=p[i-1]+p[i-2];
    for(int i=1;i<=maxn;i++){
        add(i,1);
    } 
    int tot=maxn;
    for(int i=1;i<=maxk;i++){
        for(int j=1;tot>=p[j]-j+1;j++){
            int pos=find_num(p[j]-j+1);
            add(pos,-1);tot--;
            if(j==1) sum[i].push_back(d[pos]);
            else{
                int x=sum[i][j-2]+d[pos];
                sum[i].push_back(x); 
            } 
            num[i].push_back(pos); 
        }
    }
}
int main(){
    pre_process();
    int T;
    Read(T);
    for(int t=1;t<=T;t++){
        int n,k;
        Read(n);Read(k);
        if(num[k][0]>n) printf("%d\n",-1);
        else{
            int pos=upper_bound(num[k].begin() ,num[k].end() ,n)-num[k].begin() -1;
            printf("%d\n",sum[k][pos]);
        }
    } 
    return 0;
}