Hướng dẫn giải

Gọi x là số đội 5 học sinh và y là số đội 3 học sinh. Khi đó ta có phương trình nghiệm nguyên:

5x + 3y = n,    x ≥ 0, y ≥ 0.

Tổng số đội là:

x + y.

Muốn số đội ít nhất thì cần chọn x (số đội 5 học sinh) lớn nhất có thể.

Từ phương trình:

5x + 3y = n

Lấy hai vế theo modulo 3:

5x ≡ n (mod 3).

Do:

5 ≡ 2 (mod 3),

suy ra:

2x ≡ n (mod 3).

Vì 2 là nghịch đảo của chính nó theo modulo 3 nên:

x ≡ 2n (mod 3).

Đặt:

q = ⌊n / 5⌋.

Ta cần tìm giá trị lớn nhất x ≤ q và thỏa mãn:

x ≡ 2n (mod 3).

Đặt:

r = (2 * (n % 3)) % 3;
d = (q % 3 - r + 3) % 3;
x = q - d;

Nếu x < 0 thì không tồn tại cách chia đội, in -1.

Ngược lại:

y = (n - 5x) / 3.

Đáp án là:

x + y.

Độ phức tạp:

• Thời gian: O(1) cho mỗi test.
• Bộ nhớ: O(1).