P9135 [THUPC 2023 初赛] 快速 LCM 变换

· · 题解

题传

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

发现删掉 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;
}