自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:32:20，当前版本为作者最后更新于2021-07-09 15:04:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

设 $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;
}