题解 P7704 「MCOI-09」Greedy Deletion

· · 题解

设 x=\prod_{i=1}^{\infty}p_i^{e_i}（p_i 表示第 i 个质数），则 x 为完全平方数当且仅当 \forall i\in \mathbb{N_+},2|e_i。即 x 为完全平方数当且仅当把 x 分解质因数后每个质数对应的指数为偶。

如果 S_n=\prod_{i=1}^ni 分解质因数后有若干个质数对应的指数为奇，因为当 i,j\ge2,k\in\mathbb{N_+} 时有 i^kj^k\ge i^k+j^k，所以最优策略肯定是把这些质数从集合里依次删去。

由于 S_n 本身很大，所以考虑对区间 [1,n] 里的每个正整数分解质因数，然后把每个质数对应的指数相加。这是经典问题，我们有预处理 O(n) 单次分解 O(\log{n}) 的线性筛做法。记 mn_i 为 i 的最小质因数，用线性筛筛出 mn_{1\sim n}，分解 x 时不断把 x 除以 mn_x 直至 x=1 即可。很显然单次的最坏复杂度为 O(\log{x})。这个做法还可以拓展，记 e_i 为 i 的最小质因子对应的次数，pre_i 为 mn_i^{e_i}。分解 x 时不断把 x 除以 pre_x。最坏情况下复杂度仍为 O(\log x)，但是常数小很多。

这样的复杂度是 O(\sum_{i=1}^T n_i\log n_i) 的，还是很劣。可以把所有询问操作离线下来按 n_i 排序，这样对于第 i 次询问只需要分解区间 [n_{i-1}+1,n_i] 里的正整数，总时间复杂度就变成 O(n \log{n}) 的了。

代码如下（码 \LaTeX 不易，希望能给个赞！QAQ）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#define pb push_back
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define db double
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}

const int N=5e6+5,qlr=998244353,lim=20;
int pme[N],top,mn[N],e[N],pre[N],ok[N],ask[N],a[N],od[N/10],Ans[N/10],pw[N],_k;

inline int ksm(int x,int y){
    int t=x,ans=1;
    while(y){
        if(y&1) ans=1ll*ans*t%qlr;
        t=1ll*t*t%qlr;
        y>>=1;
    }
    return ans;
}

void xxs(int n){
    fo(i,2,n){
        if(!ok[i]){
            pme[++top]=i,mn[i]=pre[i]=i,e[i]=1;
            pw[i]=ksm(i,_k);
        } 
        fo(j,1,top){
            int p=pme[j],k=i*p;
            if(k>n) break;
            ok[k]=1;
            if(i%p) mn[k]=pre[k]=p,e[k]=1;
            else{
                mn[k]=p,pre[k]=pre[i]*p,e[k]=e[i]+1;
                break;
            } 
        }
    }
}

bool cmp(int x,int y){return ask[x]<ask[y];} 

int main(){
    int T=read(),k=read(),n=read(),lst=2,ans=0;_k=k;
    xxs(n);
    fo(i,1,T) ask[i]=read(),od[i]=i;
    sort(od+1,od+1+T,cmp);
    fo(i,1,T){
        fo(j,lst,ask[od[i]]){
            int t=j;
            while(t>1){
                if(e[t]&1){
                    a[mn[t]]^=1;
                    if(a[mn[t]]) ans=(ans+pw[mn[t]])%qlr;
                    else ans=(ans-pw[mn[t]]+qlr)%qlr;
                }
                t/=pre[t];
            }
        }lst=ask[od[i]]+1;
        Ans[od[i]]=ans;
    }fo(i,1,T) printf("%d\n",Ans[i]);
    return 0;
}