nt/sigma_0_sum.hpp

• View this file on GitHub
• Last update: 2023-02-16 20:33:02+09:00
• Include: #include "nt/sigma_0_sum.hpp"

Verified with

• test_atcoder/abc230e.test.cpp

Code

// sum_[1,N] sigma_0(n)
ll sigma_0_sum(ll N) {
  assert(N <= (1LL << 50));
  ll sq = sqrtl(N);
  ll ANS = 0;
  for (int d = 1; d <= sq; ++d) { ANS += ll(double(N) / d); }
  return 2 * ANS - sq * sq;
}

#line 1 "nt/sigma_0_sum.hpp"
// sum_[1,N] sigma_0(n)
ll sigma_0_sum(ll N) {
  assert(N <= (1LL << 50));
  ll sq = sqrtl(N);
  ll ANS = 0;
  for (int d = 1; d <= sq; ++d) { ANS += ll(double(N) / d); }
  return 2 * ANS - sq * sq;
}

Back to top page