library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Euler Transform
(FPS/eulertransform.hpp)

• View this file on GitHub
• Last update: 2026-01-30 05:37:33+09:00
• Include: #include "FPS/eulertransform.hpp"

Code

#pragma once

template <typename T> Poly<T> EulerTransform(Poly<T> &f) {
    int n = SZ(f);
    Poly<Fp> g(n);
    rep(d, 1, n) {
        for (int k = d; k < n; k += d)
            g[k] += f[d] * d;
    }
    rep(d, 1, n) g[d] /= d;
    return g.exp();
}

/**
 * @brief Euler Transform
 */

#line 2 "FPS/eulertransform.hpp"

template <typename T> Poly<T> EulerTransform(Poly<T> &f) {
    int n = SZ(f);
    Poly<Fp> g(n);
    rep(d, 1, n) {
        for (int k = d; k < n; k += d)
            g[k] += f[d] * d;
    }
    rep(d, 1, n) g[d] /= d;
    return g.exp();
}

/**
 * @brief Euler Transform
 */

Back to top page