Bàn phím 2 phím (2 Keys Keyboard) trong C++

Ban đầu có 1 ký tự 'A'. Mỗi bước có thể: Copy All (sao chép toàn bộ) hoặc Paste (dán nội dung vừa copy). Tìm số bước tối thiểu để có đúng n ký tự 'A'.

Ví dụ: n=3 → 3 bước (Copy, Paste, Paste).

Quan sát & Giải pháp

Vấn đề tương đương phân tích n thành tổng các thừa số nguyên tố. Tổng các thừa số nguyên tố chính là số bước tối thiểu.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSteps(int n) {
        int ret = 0;
        for (int k = 2; k <= n; k++) {
            while (n % k == 0) {
                ret += k;
                n /= k;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.minSteps(10); // Output: 7 (2+5)
    return 0;
}

Đầu vào / Đầu ra

Input: 10

Output: 7