代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
#define mod 998244353
typedef long long ll;
#define N 400050
vector<int>V[N];
int pri[N],p_cnt,isp[N],n,m,op,a[N];
ll h1[N],h2[N],g[N],f[N],mu[N],F[N],lst[N];
ll s1(ll x) {return x*(x+1)/2%mod;}
ll pf(ll x) {return x*x%mod;}
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void sieve(int ln) {
	int i,j;mu[1]=1;
	for(i=2;i<=ln;i++) {
		if(!isp[i]) pri[++p_cnt]=i,mu[i]=-1;
		for(j=1;j<=p_cnt&&i*pri[j]<=ln;j++) {
			isp[i*pri[j]]=1;
			if(i%pri[j]==0) {mu[i*pri[j]]=0; break;}
			mu[i*pri[j]]=-mu[i];
		}
	}
}
void fix(int x,int v,int num) {
	int i,lim=V[x].size();
	ll tmp=h2[x]*num%mod;
	for(i=0;i<lim;i++) h1[V[x][i]]=(h1[V[x][i]]+(tmp-h2[x])*mu[x/V[x][i]])%mod;
	h2[x]=tmp;
}
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
	int x=0; char s=nc();
	while(s<'0') s=nc();
	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
	return x;
}
#include <ctime>
typedef double f2;
int d[N],e[N];
int main() {

	// freopen("lalaland.in","r",stdin);
	// freopen("lalaland.out","w",stdout);
	f2 tt=clock();
	int i,j;
	sieve(N-1);
n=400000,m=400000,op=0;
//	n=rd(),m=rd(),op=rd();
	//for(i=1;i<=n;i++) a[i]=rd();
	for(i=1;i<=m;i++) {
		for(j=i;j<=m;j+=i) {
			d[j]++;
			f[j]=(f[j]+mu[i]*i*i%mod*( pf(s1(j/i))-pf(s1((j-1)/i)) ))%mod;
		}
		f[i]=(f[i]+f[i-1])%mod;
	}
	for(i=1;i<=m;i++) V[i].resize(d[i]);
	for(i=1;i<=m;i++) {
		for(j=i;j<=m;j+=i) {
			V[j][e[j]++]=i;
			g[j]=(g[j]+mu[i]*(pf(lst[i]+mu[j])-pf(lst[i])))%mod;
			lst[i]=(lst[i]+mu[j])%mod;
		}
		g[i]=(g[i]+g[i-1])%mod;
	}

	// for(i=1;i<=m;i++) for(j=i;j<=m;j+=i) V[j].push_back(i);
	printf("time is %.2f\n",(clock()-tt)/1000.0);
	return 0;
	if(op==0) {
		for(i=1;i<=m;i++) h2[i]=1;
		for(i=1;i<=n;i++) {
			int lim=V[a[i]].size();
			for(j=0;j<lim;j++) {
				h2[V[a[i]][j]]=h2[V[a[i]][j]]*(f[a[i]]+1)%mod;
			}
		}
		for(i=1;i<=m;i++) h2[i]--;
		for(i=m;i;i--) {
			h1[i]=h2[i];
			for(j=i+i;j<=m;j+=i) {
				h1[i]=(h1[i]-h1[j])%mod;
			}
		}
		ll ans=0;
		for(i=1;i<=m;i++) ans=(ans+g[i]*h1[i])%mod;
		printf("%lld\n",(ans+mod)%mod);
	}else {
		int s;
		for(i=1;i<=m;i++) h2[i]=1;
		for(s=1;s<=n;s++) {
			a[s]=(19891989*F[s-1]+a[s])%m+1;
			int x=a[s];
			int lim=V[x].size();
			F[s]=F[s-1];
			for(i=0;i<lim;i++) F[s]=(F[s]-g[V[x][i]]*h1[V[x][i]])%mod;
			for(i=0;i<lim;i++) {
				fix(V[x][i],-1,f[x]+1);
			}
			for(i=0;i<lim;i++) F[s]=(F[s]+g[V[x][i]]*h1[V[x][i]])%mod;
			F[s]=(F[s]+mod)%mod;
			printf("%lld\n",F[s]);
		}
	}
}

评测结果