Tổng chữ số của số N viết trong các cơ số từ 2 đến N/2 trong C++

Cho số N. Tính tổng các chữ số khi viết N trong mọi cơ số từ 2 đến N/2.

Ví dụ

Đầu vào: N = 5

Đầu ra: 2

Giải thích: Cơ số 2: 5 = 101₂. Tổng chữ số = 1+0+1 = 2

Phương pháp

Với mỗi cơ số b từ 2 đến N/2: chia liên tiếp N cho b, cộng dồn phần dư (chữ số).

int tongChuSoCoSo(int n, int base) {
    int tong = 0;
    while (n > 0) {
        tong += n % base;
        n /= base;
    }
    return tong;
}

int tongTatCaCoSo(int n) {
    int tong = 0;
    for (int base = 2; base <= n/2; base++)
        tong += tongChuSoCoSo(n, base);
    return tong;
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int tongChuSoCoSo(int n, int base) {
    int tong = 0;
    while (n > 0) { tong += n % base; n /= base; }
    return tong;
}

int main() {
    int N = 11;
    int tong = 0;
    for (int base = 2; base <= N/2; base++)
        tong += tongChuSoCoSo(N, base);
    cout << "Tổng chữ số của " << N << " ở cơ số 2.." << N/2 << " = " << tong;
    return 0;
}

Kết quả

Tổng chữ số của 11 ở cơ số 2..5 = 14