Ước số chung lớn nhất - Bội số chung nhỏ nhất

Thuật toán tìm ước số chung lớn nhất - bội số chung nhỏ nhất

Khái niệm: Ước số chung lớn nhất của hai số nguyên a và b, ký hiêu là USCLN(a, b), là số nguyên d lớn nhất mà cả a và b đều chia hết cho d.

Công thức: USCLN(a, b) = USCLN(b, a mod b)

Nhận xét: Công thức đệ quy trên sẽ dừng khi b=0 và kết quả là a

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int USCLN(int a, int b) {

  if (b==0) return a;

  return USCLN(b, a%b);

}

Khái niệm: Bội số chung nhỏ nhất của hai số nguyên a và b, ký hiêu là BSCNN(a, b), là số nguyên d nhỏ nhất mà d đều chia hết cho cả a và b.

Công thức: BSCNN(a, b) = (a*b)/USCLN(a, b)

Nhận xét: Cả a và b đều chia hết cho USCLN(a, b) nên chúng ta có thể viết lại công thức trên để tránh việc tràn số khi tính toán phép nhân trước: BSCNN(a, b) = a/USCLN(a, b)*b;

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int BSCNN(int a, int b) {

  return a/USCLN(a, b)/b;

}