ABC185-E Adjacent GCD (約数・倍数関係の高速ゼータ・メビウス変換)
(Test/AtCoder/arc185_e.test.cpp)

View this file on GitHub
Last update: 2025-05-29 15:37:34+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://atcoder.jp/contests/arc185/submissions/66241326
Link: https://atcoder.jp/contests/arc185/tasks/arc185_e

整数 $a, b$ に関して $a$ が $b$ の約数であることを $a\mid b$ と表記する。

約数関係のメビウス変換

$x_{i} = \sum_{j\mid i} y_{j}$ を満たす $x, y$ に対して、 $x$ から $y$ を $\Theta (N\log \log N)$ で得ることができる。

for (int p = 1 ; p <= MAX ; p++) if (p is prime) {
    for (int k = MAX / p ; k >= 1 ; k--) x[p * k] -= x[k];
}

約数関係のゼータ変換

$x_{i} = \sum_{j\mid i} y_{j}$ を満たす $x, y$ に対して、 $y$ から $x$ を $\Theta (N\log \log N)$ で得ることができる。

for (int p = 1 ; p <= MAX ; p++) if (p is prime) {
    for (int k = 1 ; p * k <= MAX ; k++) y[p * k] += y[k];
}

倍数関係のメビウス変換

$x_{i} = \sum_{i\mid j} y_{j}$ を満たす $x, y$ に対して、 $x$ から $y$ を $\Theta (N\log \log N)$ で得ることができる。

for (int p = 1 ; p <= MAX ; p++) if (p is prime) {
    for (int k = 1 ; k * p <= MAX ; k++) x[k] -= x[p * k];
}

倍数関係のゼータ変換

$x_{i} = \sum_{i\mid j} y_{j}$ を満たす $x, y$ に対して、 $y$ から $x$ を $\Theta (N\log \log N)$ で得ることができる。

for (int p = 1 ; p <= MAX ; p++) if (p is prime) {
    for (int k = 1 ; k * p <= MAX ; k++) y[k] += y[p * k];
}

コンテスト中

どっちがどっちだが頭が壊れた -> $1$ の方に値が集まっているなら倍数関係、 $N$ の方に値が集まっているなら約数関係

包除原理とか考えると大体嵌る。多次元累積和をとっていると考えて向きを考えるとすっと変換の式が書けるはず。

ゼータ・メビウス変換をする上で、メビウス関数を陽に求める必要は無い。また、考察上でも変換するだけならメビウス関数は出てこない。

参考

ユーザー解説 ARC185-E

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/arc185/tasks/arc185_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Regular Contest 185 - E Adjacent GCD
 * https://atcoder.jp/contests/arc185/submissions/66241326
 */

#include "../../Src/Number/LinearSieve.hpp"
using namespace zawa;
#include "atcoder/modint"
using mint = atcoder::modint998244353;

#include <iostream>
#include <vector>
#include <numeric>

const int MAX = 100000;
int N, A[500050];
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    LinearSieve siv{MAX + 1};
    std::vector<mint> x(MAX + 1), a(MAX + 1);
    // 重みの列Y
    std::iota(x.begin(), x.end(), mint::raw(0));
    // mobius transformでXを得る
    for (int i = 1 ; i <= MAX ; i++) if (siv.isPrime(i)) {
        for (int j = MAX / i ; j >= 1 ; j--) x[i * j] -= x[j];
    }
    std::vector<mint> p2(N, mint::raw(1));
    for (int i = 1 ; i < N ; i++) p2[i] *= p2[i - 1] * mint::raw(2);
    mint ans = 0;
    for (int i = 0 ; i < N ; i++, ans *= mint::raw(2)) {
        for (int d : siv.divisor<int>(A[i])) {
            ans += x[d] * a[d];
            a[d] += p2[i];
        }
        std::cout << ans.val() << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

ABC185-E Adjacent GCD (約数・倍数関係の高速ゼータ・メビウス変換) (Test/AtCoder/arc185_e.test.cpp)