fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. const int MAX_VALUE = 1000; // Đặt giá trị khởi tạo lớn cụ thể cho minCount
  7. int minCount = MAX_VALUE;
  8. vector<int> bestSolution;
  9.  
  10. void backtrack(int M, int N, vector<int>& solution, int start) {
  11. // Dừng khi tử số về 0
  12. if (M == 0) {
  13. if (solution.size() < minCount) {
  14. minCount = solution.size();
  15. bestSolution = solution;
  16. }
  17. return;
  18. }
  19.  
  20. // Trừ dần cho các phân số bé hơn nó
  21. for (int k = start; k <= (N + M - 1) / M; ++k) {
  22. // Tính toán tử số mới và mẫu số mới sau khi trừ phân số 1/k
  23. int newM = M * k - N;
  24. int newN = N * k;
  25.  
  26. // Nếu tử số nhỏ hơn 0, tiếp tục
  27. if (newM < 0) continue;
  28.  
  29. // Thêm phân số 1/k vào giải pháp hiện tại
  30. solution.push_back(k);
  31. backtrack(newM, newN, solution, k + 1); // Tiếp tục với k + 1 để tránh lặp lại các phân số
  32. solution.pop_back(); // Quay lui để thử nghiệm phân số khác
  33. }
  34. }
  35.  
  36. int main() {
  37. int M, N;
  38. cin >> M >> N;
  39.  
  40. vector<int> solution;
  41. backtrack(M, N, solution, 1);
  42.  
  43. cout << minCount << endl;
  44. for (int k : bestSolution) {
  45. cout << "1/" << k << " ";
  46. }
  47. cout << endl;
  48.  
  49. return 0;
  50. }
  51.  
Success #stdin #stdout 0s 5288KB
stdin
3 4
stdout
2
1/2 1/4