卷积

2023-10-23 | 阅读：次

===

Index

gcd_lcm卷积模板
gcd卷积
gcd pair之和
统计gcd数对
lcm卷积

gcd_lcm卷积模板

template <class T> void multiple_zeta(vector<T> &f) {
    int N = int(f.size()) - 1;
    vector<char> is_prime(N + 1, 1);
    for (int p = 2; p <= N; p++) if (is_prime[p]) {
        for (int q = p * 2; q <= N; q += p) is_prime[q] = 0;
        for (int j = N / p; j > 0; --j) f[j] += f[j * p];
    }
}
// inverse of multiple_zeta O(N loglog N)
template <class T> void multiple_moebius(vector<T> &f) {
    int N = int(f.size()) - 1;
    vector<char> is_prime(N + 1, 1);
    for (int p = 2; p <= N; p++) if (is_prime[p]) {
        for (int q = p * 2; q <= N; q += p) is_prime[q] = 0;
        for (int j = 1; j * p <= N; ++j) f[j] -= f[j * p];
    }
}
// 对于n的所有约数m,求f(m)的总和 O(N loglog N)
template <class T> void divisor_zeta(vector<T> &f) {
    int N = int(f.size()) - 1;
    vector<char> is_prime(N + 1, 1);
    for (int p = 2; p <= N; ++p) if (is_prime[p]) {
        for (int q = p * 2; q <= N; q += p) is_prime[q] = 0;
        for (int j = 1; j * p <= N; ++j) f[j * p] += f[j];
    }
}
// inverse of divisor_zeta()
template <class T> void divisor_moebius(vector<T> &f) {
    int N = int(f.size()) - 1;
    vector<char> is_prime(N + 1, 1);
    for (int p = 2; p <= N; ++p) if (is_prime[p]) {
        for (int q = p * 2; q <= N; q += p) is_prime[q] = 0;
        for (int j = N / p; j > 0; --j) f[j * p] -= f[j];
    }
} 
// GCD convolution, ret[k] = \sum_{gcd(i, j) = k} f[i] * g[j]
template <class T> vector<T> gcdconv(vector<T> f, vector<T> g) {
    assert(f.size() == g.size());
    multiple_zeta(f); multiple_zeta(g);
    for (int i = 0; i < int(g.size()); ++i) f[i] *= g[i];
    multiple_moebius(f);
    return f;
}
// LCM convolution ret[k] = \sum_{lcm(i, j) = k} f[i] * g[j]
template <class T> vector<T> lcmconv(vector<T> f, vector<T> g) {
    assert(f.size() == g.size());
    divisor_zeta(f); divisor_zeta(g);
    for (int i = 0; i < int(g.size()); ++i) f[i] *= g[i];
    divisor_moebius(f);
    return f;
}

gcd卷积

gcd conv

给定两个长为n的数组a,b 求 c1,c2,…cn，其中ck 表示对所有满足gcd(i,j)=k的下标对(i,j) a[i]与b[j]乘积的和，模998244353。

1 <= n <= 1e6
0 <= ai, bi < 998244353

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N;
    cin >> N;
    std::vector<mint> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];
    auto ret = gcdconv(A, B);
    for (int i = 1; i <= N; ++i) cout << ret[i] << (i == N ? '\n' : ' ');
}

gcd_pair之和

输入n，求1-n n个元素组成所有满足1<=i<j<=n 的(i,j)对的gcd之和。

1 <= n <= 5e5

分析

直接对1-n的数组进行gcd卷积，获取数组c,c[k]表示满足gcd(i,j)=k的(i,j)对数量，由于需要满足i<j,所以答案需要除以2.

void ac_yyf(int tt) {
    cin >> n;
    vector<long long> a(n + 1, 1);
    a[0] = 0;
    auto c = gcdconv(a, a);
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += i * 1ll * (c[i] - 1); // 减去(i,i)自身
    }
    cout << ans / 2 << '\n';
}

统计gcd数对

cf1884d

给定一个数组a，统计有多少个(i,j)对满足 1<=i<j<=n 且不存在一个1<=k<=n，使得 a[i]整数a[k]且a[j]整除a[k].

1 <= n <= 1e6
1 <= a[i] <= 1e6

分析

gcd卷积，求出以每个k为gcd的pair对数目，如果k不是某个a[i]的倍数，则将以k为gcd的pair对数目加到答案中。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
    }
    vector<long long> f(n+1);
    for(int x:a) f[x]++;
    auto g=gcdconv(f,f);
    vector<char> p(n+1,0);
    for(int i=1;i<=n;++i){
        if(!f[i]) continue;
        for(int j=i;j<=n;j+=i)p[j]=1;
    }
    ll c=0;
    for(int i=1;i<=n;++i){
        if(!p[i])c+=g[i];
    }
    c/=2;
    cout<<c<<'\n';
 
}

lcm卷积

lcm conv

给定两个长为n的数组a,b 求 c1,c2,…cn，其中ck 表示对所有满足lcm(i,j)=k的下标对(i,j) a[i]与b[j]乘积的和，模998244353。

1 <= n <= 1e6
0 <= ai, bi < 998244353

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N;
    cin >> N;
    std::vector<mint> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];
    auto ret = lcmconv(A, B);
    for (int i = 1; i <= N; ++i) cout << ret[i] << (i == N ? '\n' : ' ');
}

king-yyf