ARC185E 题解

· · 题解

直接求不好求，考虑算贡献。那么：

ans_i=\sum_{x=2}^i\sum_{y=1}^{x-1}\gcd(a_x,a_y)2^{i-(x-y+1)}

其中有若干有序对 (x,y) 重叠，可以发现如下事实：

ans_i=2ans_{i-1}+\sum_{y=1}^{i-1}\gcd(a_i,a_y)2^{y-1}

因此只需要对于每个 i 计算：

\sum_{y=1}^{i-1}\gcd(a_i,a_y)2^{y-1}

考虑欧拉反演，

\sum_{y=1}^{i-1}2^{y-1}\sum_{d|\gcd(a_i,a_y)}\varphi(d)

由于 \gcd(a_i,a_y) 的因数也必然是 a_i 的因数，因此可写作：

\sum_{d|a_i}\varphi(d)\sum_{y=1}^{i-1}2^{y-1}[d|a_y]

记 g_i=\sum_{y=1}^{i-1}2^{y-1}[i|a_y]

\sum_{d|a_i}\varphi(d)g_d

求这个式子是 O(\sigma(a_i)) 的，其中 \sigma(a_i) 表示其因数个数。

只需要维护 g 即可，每次考虑加入 a_i，枚举其因数 d，使 g_d \larr g_d+2^{i-1} 即可，这也是 O(\sigma(a_i)) 的。

由于 \max_{i=1}^{10^5}\sigma(i)=128，不严谨的表示一下复杂度为 O(128n)，可过，最慢点大概不超过 500ms。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
#define N 500005
#define V 100005
//#define pii pair<int,int>
//#define fi first
//#define se second
//#define rep(i,j,k) for(int i=j;i<=k;i++)
int fpow(int x,int y){
    int ret=1,op=x;
    op%=mod;
    while(y){
        if(y&1)ret=ret*op%mod;
        op=op*op%mod;
        y>>=1;
    }
    return ret;
}
int a[N];
int n;
int vis[V];
int val[V];
vector<int>d[V];
void init(){
    for(int i=1;i<=V-5;i++){
        for(int j=i;j<=V-5;j+=i){
            d[j].push_back(i);
        }
    }
    for(int i=1;i<=V-5;i++){
        val[i]=i;
        for(int v:d[i])if(v!=i)val[i]-=val[v];
        val[i]=(val[i]%mod+mod)%mod;
    }
}
int ans[V];
int f[N];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int v:d[a[i]])f[i]=(f[i]+ans[v])%mod;
        int o=fpow(2,i-1);
        // int o=1;
        for(int v:d[a[i]])ans[v]=(ans[v]+o*val[v])%mod;
    }
    for(int i=2;i<=n;i++)f[i]=(f[i]+f[i-1]*2)%mod;
    for(int i=1;i<=n;i++)cout<<f[i]<<'\n';
    return 0;
}