Giả sử chúng ta có một số n. Chúng ta thực hiện bất kỳ phép toán nào trong số sau đây tùy ý số lần:
Thay n bằng n/2 khi n chia hết cho 2
Thay n bằng 2n/3 khi n chia hết cho 3
Thay n bằng 4n/5 khi n chia hết cho 5
Chúng ta phải đếm số phép toán tối thiểu cần thiết để làm cho số thành 1. Nếu không thể, trả về -1.
Ví dụ, nếu đầu vào là n = 10, thì đầu ra sẽ là 4, vì dùng n/2 được 5, rồi 4n/5 được 4, rồi n/2 lại được 2 và n/2 lại được 1.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
m := 0 while n khác 1, do: if n mod 2 giống 0, thì: n := n / 2 (tăng m lên 1) ngược lại khi n mod 3 giống 0, thì: n := n / 3 m := m + 2 ngược lại khi n mod 5 giống 0, thì: n := n / 5 m := m + 3 Ngược lại m := -1 Thoát khỏi vòng lặp return m
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(int n) { int m = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; m++; } else if (n % 3 == 0) { n = n / 3; m += 2; } else if (n % 5 == 0) { n = n / 5; m += 3; } else { m = -1; break; } } return m; } int main() { int n = 10; cout << solve(n) << endl; }Đầu vào
10
Đầu ra
4