floor_sum
(src/math/floor_sum.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/floor_sum.hpp"

floor_sum

ll floor_sum(ll n, ll m, ll a, ll b)

\[\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor\]

を返します．

制約

• $0 \leq n \leq 10^9$
• $1 \leq m \leq 10^9$
• 答えがオーバーフローしないこと．

計算量

• $O(\log (n + m + a + b))$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/number_theory/sum_of_floor_of_linear.test.cpp

Code

#pragma once
#include "../template/template.hpp"
constexpr long long floor_sum(const long long n, const long long m, long long a, long long b) {
    long long res = 0;
    if(a >= m) res += (n - 1) * n * (a / m) / 2, a %= m;
    if(b >= m) res += n * (b / m), b %= m;
    const long long y = (a * n + b) / m;
    if(y == 0) return res;
    const long long x = y * m - b;
    res += (n - (x + a - 1) / a) * y;
    res += floor_sum(y, a, m, (a - x % a) % a);
    return res;
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/floor_sum.hpp"
constexpr long long floor_sum(const long long n, const long long m, long long a, long long b) {
    long long res = 0;
    if(a >= m) res += (n - 1) * n * (a / m) / 2, a %= m;
    if(b >= m) res += n * (b / m), b %= m;
    const long long y = (a * n + b) / m;
    if(y == 0) return res;
    const long long x = y * m - b;
    res += (n - (x + a - 1) / a) * y;
    res += floor_sum(y, a, m, (a - x % a) % a);
    return res;
}

Back to top page