自动搬运

查看原文

来自洛谷，原作者为

	Mobius127 Countless stars are like dust

搬运于2025-08-24 22:45:41，当前版本为作者最后更新于2023-03-07 22:56:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题传

赛时想着莫反去了，有点可惜没想出来，实际上还是挺有趣的。

发现删掉 $a_{i}, a_{j}$ 再加上 $a_{i}+a_{j}$ 很不好算，要是能有什么东西能将三个操作的贡献独立分开就好了。

考虑所有数为 $2^{x}$ 的情况，如果一对 $(i,j)$ 会改变原来的 $\operatorname{lcm}$，那么 $i/j$ 至少有一个是 $2$ 的最高次幂，现在假定最高的是 $i$，看 $j$ 和次高的关系。

1. 若 $x_{j}<x_{i}$，则 $i$ 的贡献是 $2^{mx'-x_{i}}$（$mx'$ 是次大值），$j$ 不会产生任何贡献，此时 $a_{i}=2^{k'} a_{j}$，那么 $a_{i}+a_{j}=(2^{k'}+1)a_{j}$，即其指数为 $x_{j}$ 不会产生贡献。

2. 若 $x_{i}=x_{j}$，那么 $a_{i}+a_{j}$ 会多分出一个 $2^{1}$。

不妨令 $h(x)$ 为删掉一个 $x$ 后 $\operatorname{lcm}$ 的变化系数，$g(x)$ 为新增一个 $x$ 后 $\operatorname{lcm}$ 的变化系数。根据上面的讨论，$h(a_{i}),h(a_{j}), g(a_{i}+a_{j})$ 中最多有一个不为 $1$，新的 $\operatorname{lcm}$ 可以用原 $\operatorname{lcm}$ 乘上三者的积得到。

不难推广到多个质数的情况（因为质数之间互不影响）。

那么答案即为

$$\sum_{i<j} \operatorname{lcm}(a_{k})g(a_{i}+a_{j})h(a_{i})h(a_{j}) $$$$=\operatorname{lcm}(a_{k})\sum_{k} g(k) \sum_{a_{i}+a_{j}=k} h(a_{i})h(a_{j}) $$

后面的求和直接卷积做就好了，复杂度 $O(A\log A)$，$A$ 是值域。

Code:

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f3f;
const int cp=998244353;
inline int mod(int x){if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline void plust(int &x, int y){x=mod(x+y);return ;}
inline void minut(int &x, int y){x=mod(x-y);return ;}
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%cp)
		if(b&1) ret=1ll*ret*a%cp;
	return ret;
}
const int g0=3;
const int invg=ksm(g0);
const int inv2=ksm(2);
const int N=5e5+5;
const int M=1.5e3+5;
const int S=2.1e6+5;
const int T=2e6;
const int Pcnt=240;
int n, tot, ans, LCM, pr[Pcnt], mn[S], inv[S], a[N], mx[S], cmx[S];
int g[S], h[N], len=1<<21, f[S], to[S];
void init(){
	n=read();for(int i=1; i<=n; ++i) a[i]=read();inv[0]=inv[1]=1;
	for(int i=2; i<=T; ++i) inv[i]=1ll*(cp-cp/i)*inv[cp%i]%cp;
	mn[1]=1;for(int i=2; i<=T; ++i) if(!mn[i]) for(int j=i; j<=T; j+=i) mn[j]=i;
	for(int i=1; i<=n; ++i){
		int x=a[i];
		while(x>1){
			int p=mn[x], s=1;
			while(mn[x]==p) x/=p, s*=p;
			if(mx[p]<s) swap(mx[p], s);
			if(cmx[p]<s) swap(cmx[p], s);
		}
	}
	LCM=1;
	for(int i=1; i<=T; ++i) if(mx[i]) LCM=1ll*LCM*mx[i]%cp;
	for(int i=1; i<=n; ++i){
		int x=a[i], t=LCM;
		while(x>1){
			int p=mn[x], s=1;
			while(mn[x]==p) x/=p, s*=p;
			if(cmx[p]<s) t=1ll*t*inv[s]%cp*max(1, cmx[p])%cp;
		}
		h[i]=t;
	}
	for(int i=1; i<=T; ++i){
		int x=i, t=LCM;
		while(x>1){
			int p=mn[x], s=1;
			while(mn[x]==p) x/=p, s*=p;
			if(mx[p]<s) t=1ll*t*inv[mx[p]]%cp*s%cp;
		}
		g[i]=t;
	}
}
void NTT(int *F, int flag){
	for(int i=0; i<len; i++)
		if(i<to[i]) swap(F[i], F[to[i]]);
	for(int s=2; s<=len; s<<=1){
		int size=s>>1;
		int omega=ksm(flag>0?g0:invg, (cp-1)/s);
		for(int L=0; L<len; L+=s){
			int buf=1;
			for(int i=L; i<L+size; i++, buf=1ll*omega*buf%cp){
				int F2=1ll*buf*F[i+size]%cp;
				F[i+size]=mod(F[i]-F2);
				F[i]=mod(F[i]+F2);
			}
		}
	}
	if(~flag) return ;int invlen=ksm(len);
	for(int i=0; i<=len; ++i) F[i]=1ll*F[i]*invlen%cp;
}
signed main(){
	init();
	memset(f, 0, sizeof(f));
	for(int i=1; i<=n; ++i) plust(f[a[i]], h[i]);
	for(int i=0; i<=len; i++) to[i]=(to[i>>1]>>1)|((i&1)?len>>1:0);
	NTT(f, 1);
	for(int i=0; i<=len; ++i) f[i]=1ll*f[i]*f[i]%cp;
	NTT(f, -1);
	for(int i=1; i<=n; ++i) minut(f[a[i]+a[i]], 1ll*h[i]*h[i]%cp);
	// for(int i=1; i<=8; ++i) printf("%d*%d ", f[i], g[i]);
	for(int i=1; i<=T; ++i) plust(ans, 1ll*f[i]*g[i]%cp);
	LCM=1ll*LCM*LCM%cp;LCM=ksm(LCM);
	ans=1ll*ans*LCM%cp;ans=1ll*ans*inv2%cp;
	printf("%d\n", ans);
	return 0;
}