Tìm ước số có tổng chữ số lớn nhất của n trong C++

Cho số nguyên n. Nhiệm vụ: tìm ước số của n có tổng chữ số lớn nhất.

Mô tả: Tìm ước số của n mà tổng các chữ số của nó là lớn nhất.

Ví dụ:

Đầu vào: 18

Đầu ra: 9

Giải thích:

Ước của 18: 1, 2, 3, 6, 9, 18. Tổng chữ số max là 9.

Phương pháp giải

Tìm tất cả ước số, tính tổng chữ số từng ước, trả về max.

Tối ưu: duyệt đến sqrt(n), tìm cặp ước (i, n/i), giảm độ phức tạp xuống O(sqrt(n)).

Chương trình minh họa

Ví dụ (cách đơn giản)

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum = sum + n % 10;
        n = n / 10;
    }
    return sum;
}

int largestDigitSumdivisior(int n) {
    int maxSum = 0;
    for (int i = 1; i <= n; i++)
        if (n % i == 0)
            maxSum = max(maxSum, calcDigitSum(i));
    return maxSum;
}

int main() {
    int n = 45;
    cout << "The divisor with largest sum of digits is " << largestDigitSumdivisior(n) << endl;
    return 0;
}

Kết quả

The divisor with largest sum of digits is 9

Ví dụ (tối ưu O(sqrt(n)))

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum = sum + n % 10;
        n = n / 10;
    }
    return sum;
}

int largestDigitSumdivisior(int n) {
    int maxSum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            maxSum = max(maxSum, calcDigitSum(i));
            maxSum = max(maxSum, calcDigitSum(n / i));
        }
    }
    return maxSum;
}

int main() {
    int n = 32;
    cout << "The divisor with largest sum of digits is " << largestDigitSumdivisior(n) << endl;
    return 0;
}

Kết quả

The divisor with largest sum of digits is 8