nt/digit_sum.hpp

View this file on GitHub
Last update: 2024-06-06 03:38:35+09:00
Include: #include "nt/digit_sum.hpp"

Required by

bigint/base.hpp

Verified with

test/1_mytest/bigint.test.cpp
test/1_mytest/digit_sum.test.cpp
test/2_library_checker/big_integer/addition_of_bigintegers.test.cpp
test/2_library_checker/big_integer/multiplication_of_bigintegers.test.cpp
test/2_library_checker/sample/aplusb128.test.cpp
test/3_yukicoder/2440.test.cpp
test/3_yukicoder/2508.test.cpp
test/3_yukicoder/2525.test.cpp
test/3_yukicoder/2580.test.cpp
test/3_yukicoder/2649.test.cpp
test/3_yukicoder/303.test.cpp
test/4_aoj/NTL_2_A.test.cpp
test/4_aoj/NTL_2_B.test.cpp
test/4_aoj/NTL_2_C.test.cpp
test/5_atcoder/abc333g.test.cpp
test/5_atcoder/abc339f.test.cpp

Code

#pragma once

int digit_sum(u64 x) {
  const int K = 100'000;
  static vc<int> dp(K);
  if (dp[1] == 0) { FOR(x, 1, K) dp[x] = dp[x / 10] + (x % 10); }
  int res = 0;
  while (x) {
    res += dp[x % K];
    x /= K;
  }
  return res;
}

#line 2 "nt/digit_sum.hpp"

int digit_sum(u64 x) {
  const int K = 100'000;
  static vc<int> dp(K);
  if (dp[1] == 0) { FOR(x, 1, K) dp[x] = dp[x / 10] + (x % 10); }
  int res = 0;
  while (x) {
    res += dp[x % K];
    x /= K;
  }
  return res;
}