cpp/number_theory/floor_sum.hpp

• View this file on GitHub
• Last update: 2024-11-03 09:29:45+09:00
• Include: #include "cpp/number_theory/floor_sum.hpp"

Depends on

• 共通ヘッダー (cpp/template/small_template.hpp)

Code

#pragma once
#include "template/small_template.hpp"

constexpr ll safe_mod(ll x, ll m) {
  x %= m;
  if (x < 0) {
    x += m;
  }
  return x;
}

// ACL
// sum[i=0 .. n-1] floor((a*i + b) / m)
ull floor_sum_unsigned(ull n, ull m, ull a, ull b) {
  ull ans = 0;
  while (true) {
    if (a >= m) {
      ans += n * (n - 1) / 2 * (a / m);
      a %= m;
    }
    if (b >= m) {
      ans += n * (b / m);
      b %= m;
    }

    ull y_max = a * n + b;
    if (y_max < m) {
      break;
    }
    n = (ull)(y_max / m);
    b = (ull)(y_max % m);
    swap(m, a);
  }
  return ans;
}

// ACL
// sum[i=0 .. n-1] floor((a*i + b) / m)
// 0 <= n < 2^32
// 1 <= m < 2^32
ll floor_sum(ll n, ll m, ll a, ll b) {
  assert(0 <= n && n < (1ll << 32));
  assert(1 <= m && m < (1ll << 32));
  ull ans = 0;
  if (a < 0) {
    ull a2 = safe_mod(a, m);
    ans -= (ull)n * (n - 1) / 2 * ((a2 - a) / m);
    a = a2;
  }
  if (b < 0) {
    ull b2 = safe_mod(b, m);
    ans -= (ull)n * ((b2 - b) / m);
    b = b2;
  }
  return ans + floor_sum_unsigned(n, m, a, b);
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/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.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/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.12.0/x64/lib/python3.12/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: template/small_template.hpp: line -1: no such header

Back to top page