LGP7704题解

来一个特别暴力的做法。

首先，如果删掉 \(x\) 和 \(y\) 的效果一定和删掉 \(xy\) 的效果相同，且代价一定不大于后者。

于是我们只删除质数，题目就变成了寻找 \(i!(1 \leq i \leq \max n)\) 中有多少个质数出现了奇数次。

给差分一下，变成求 \(i\) 的质因子分解。

有人可能会认为这里需要用到 PR，其实并不需要，因为所有的 \(i \leq \max n\)，所以只需要记录下每一个 \(i\) 最小的质因子，然后直接跳即可。

复杂度的话，\(i\) 的质因子总数一定不超过 \(\log_2 i\)（最坏情况是存在一个 \(k\) 使得 \(i=2^k\)），所以复杂度是 \(O(n\log \log n+T)\) 的，且常数较小

加上快读&快输&加减法优化&整数除法转实数乘法&预处理逆元后最大点才 349ms，轻松通过。

ps:这题思维难度和代码难度都不高，评绿吧。。。

#include<cstdlib>

#include<cstdio>

#include<cctype>

const int M=5e6+5,mod=998244353;

int T,n,k,top,p[M],ans[M],pri[M],pos[M];bool vis[M];

double inv[M];

inline int read(){

	int n=0;char s;

	while(!isdigit(s=getchar()));

	while(n=n*10+(s^48),isdigit(s=getchar()));

	return n;

}

inline void write(int n){

	char s[10];int top=0;

	while(s[++top]=n%10^48,n/=10);

	while(putchar(s[top]),--top);

}

inline int Add(const int&a,const int&b){

	return a+b>=mod?a+b-mod:a+b;

}

inline int Del(const int&a,const int&b){

	return b>a?a-b+mod:a-b;

}

inline int pow(int a,int b){

	int ans=1;

	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;

	return ans;

}

inline void sieve(const int&M){

	register int i,j,x;

	for(i=2;i<=M;++i){

		ans[x=i]=ans[i-1];

		if(!pos[i]){

			pri[pos[i]=++top]=i;inv[top]=1./i+1e-15;

			ans[i]=Add(ans[i],p[top]=pow(i,k));vis[top]=1;

		}

		else{

			while(x^1){

				ans[i]=(vis[pos[x]]^=1)?Add(ans[i],p[pos[x]]):Del(ans[i],p[pos[x]]);

				x=x*inv[pos[x]];

			}

		}

		for(j=1;(x=i*pri[j])<=M;++j)if((pos[x]=j)==pos[i])break;

	}

}

signed main(){

	register int i;

	T=read();k=read();sieve(read());

	while(T--)write(ans[read()]),putchar(10);

}

巴特西

LGP7704题解

最新文章

热门文章