ARC185E 题解

· · 个人记录

这个故事告诉我们看见 \gcd 只会想莫反的人都完蛋了。

令 f_{i} 表示以 i 结尾的所有子序列的和，显然有 f_{i}=\sum_{j=1}^{i-1}(f_{j}+2^{j-1}\gcd(a_i,a_j))，m=i 的答案即为 \sum_{i\le m}f_i。

前半部分的 f_j 显然可以直接记录，所以只需要快速计算 \sum_{j=1}^{i-1}2^{j-1}\gcd(a_i,a_j)。

如果你跟我一样推莫反式子就会很复杂，考虑到有个著名的狄利克雷卷积式 \varphi\times I=Id，也就是 \sum_{d\mid n}\varphi(d)=n。

代入上面的式子：

\begin{aligned} &\ \ \ \ \ \sum_{j=1}^{i-1}2^{j-1}\gcd(a_i,a_j)\\ &=\sum_{j=1}^{i-1}2^{j-1}\sum_{d\mid a_i,d\mid a_j}\varphi(d)\\ &=\sum_{d\mid a_i}\varphi(d)\sum_{j=1}^{i-1}2^{j-1}[d\mid a_j] \end{aligned}

到这里就显而易见了，枚举 a_i 的因数 d，开桶记录 i 之前是 d 的倍数的 a_j 的 2^{j-1} 之和即可。

时间复杂度 O(n\max d(a_i))，可以通过。

#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
#define deb(x) cerr << #x"=" << x << '\n';
using namespace std;
const int N = 5e5 + 5, mod = 998244353;
int n, a[N], f[N], g[N], pw[N];
vector<int> d[N];
int cnt, pri[N], phi[N];
bool isprime[N];
void sieve(int n){
    isprime[1] = phi[1] = 1;
    For(i, 2, n){
        if(!isprime[i]) pri[++cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt && i * pri[j] <= n; j++){
            isprime[i * pri[j]] = 1;
            if(i % pri[j]) phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            else {phi[i * pri[j]] = phi[i] * pri[j]; break;}
        }
    }
    pw[0] = 1;
    For(i, 1, n) pw[i] = pw[i - 1] * 2 % mod;
}
void Solve(){
    sieve(500000);
    cin >> n;
    For(i, 1, n){
        cin >> a[i];
        for(int j = 1; j * j <= a[i]; j++){
            if(a[i] % j) continue;
            d[i].push_back(j);
            if(j * j != a[i]) d[i].push_back(a[i] / j);
        }
    }
    int sum = 0;
    For(i, 1, n){
        f[i] = sum;
        for(int x : d[i]) f[i] = (f[i] + phi[x] * g[x] % mod) % mod;
        for(int x : d[i]) g[x] = (g[x] + pw[i - 1]) % mod;
        sum = (sum + f[i]) % mod;
        cout << sum << '\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1; //cin >> T;
    while(T--) Solve();
    return 0;
}