ƯỚC - BỘI
Bộ đề tin học: Bài 1 đến Bài 5
Bài 1. Bội chung nhỏ nhất trong đoạn
Mô tả
Cho ba số nguyên dương a, b, c và hai số nguyên dương L, R.
Hãy tìm số nguyên dương nhỏ nhất n sao cho:
L <= n <= Rnchia hết choanchia hết chobnchia hết choc
Nếu không tồn tại số như vậy, in ra -1.
Dữ liệu vào
Gồm một dòng chứa 5 số nguyên dương a, b, c, L, R.
Dữ liệu ra
In ra số nguyên dương nhỏ nhất thỏa mãn yêu cầu, hoặc -1 nếu không tồn tại.
Ràng buộc
1 <= a, b, c <= 10^61 <= L <= R <= 10^18
Ví dụ
Input
18 21 24 100 999
Output
504
Giải thích
Ta có BCNN(18, 21, 24) = 504.
Số 504 thuộc đoạn [100, 999], nên đáp án là 504.
Bài 2. Số học sinh trong đoạn
Mô tả
Cho k số nguyên dương a1, a2, ..., ak và một đoạn [L, R].
Hãy tìm số nguyên dương nhỏ nhất n sao cho:
L <= n <= Rnchia hết cho tất cả các sốa1, a2, ..., ak
Nếu không tồn tại, in ra -1.
Dữ liệu vào
- Dòng 1 chứa số nguyên dương
k. - Dòng 2 chứa
ksố nguyên dươnga1, a2, ..., ak. - Dòng 3 chứa hai số nguyên dương
L,R.
Dữ liệu ra
In ra số nguyên dương nhỏ nhất thỏa mãn yêu cầu, hoặc -1 nếu không tồn tại.
Ràng buộc
1 <= k <= 201 <= ai <= 10^61 <= L <= R <= 10^18
Ví dụ
Input
4
3 4 7 9
1600 2000
Output
1764
Giải thích
Ta có BCNN(3, 4, 7, 9) = 252.
Bội nhỏ nhất của 252 nằm trong đoạn [1600, 2000] là 1764.
Bài 3. Xếp bó sách
Mô tả
Cho k số nguyên dương a1, a2, ..., ak và một đoạn [L, R].
Hãy tìm số nguyên dương lớn nhất n sao cho:
L <= n <= Rnchia hết cho tất cả các sốa1, a2, ..., ak
Nếu không tồn tại, in ra -1.
Dữ liệu vào
- Dòng 1 chứa số nguyên dương
k. - Dòng 2 chứa
ksố nguyên dươnga1, a2, ..., ak. - Dòng 3 chứa hai số nguyên dương
L,R.
Dữ liệu ra
In ra số nguyên dương lớn nhất thỏa mãn yêu cầu, hoặc -1 nếu không tồn tại.
Ràng buộc
1 <= k <= 201 <= ai <= 10^61 <= L <= R <= 10^18
Ví dụ
Input
3
8 12 15
400 500
Output
480
Giải thích
Ta có BCNN(8, 12, 15) = 120.
Các bội của 120 trong đoạn [400, 500] là 480, nên đáp án là 480.
Bài 4. Xếp hàng nhiều nhất
Mô tả
Cho số nguyên dương n là số học sinh của một lớp.
Hãy xác định số hàng nhiều nhất có thể xếp sao cho:
- các hàng có cùng số học sinh
- mỗi hàng có ít nhất
mhọc sinh - không có học sinh nào lẻ hàng
Nếu không thể xếp được, in ra 0.
Dữ liệu vào
Gồm một dòng chứa hai số nguyên dương n và m.
Dữ liệu ra
In ra số hàng nhiều nhất có thể xếp.
Ràng buộc
1 <= n <= 10^121 <= m <= n
Ví dụ
Input
45 2
Output
15
Giải thích
Để số hàng là nhiều nhất thì số học sinh trong mỗi hàng phải là ước nhỏ nhất của 45 nhưng không nhỏ hơn 2.
Ở đây số học sinh mỗi hàng nhỏ nhất có thể là 3, nên số hàng là 45 / 3 = 15.
Bài 5. Chia thành nhiều tổ nhất
Mô tả
Cho k số nguyên dương a1, a2, ..., ak, trong đó ai là số lượng của loại thứ i.
Hãy chia thành nhiều tổ nhất sao cho số lượng mỗi loại được chia đều vào các tổ.
Dữ liệu vào
- Dòng 1 chứa số nguyên dương
k. - Dòng 2 chứa
ksố nguyên dươnga1, a2, ..., ak.
Dữ liệu ra
In ra số tổ nhiều nhất có thể chia.
Ràng buộc
1 <= k <= 201 <= ai <= 10^12
Ví dụ
Input
2
24 108
Output
12
Giải thích
Số tổ nhiều nhất chính là UCLN(24, 108) = 12.
Bộ đề tin học: Bài 6 đến Bài 10
Bài 6. Lần gặp tiếp theo
Mô tả
Hai bạn A và B cùng thực hiện một hoạt động theo chu kỳ.
- Bạn A cứ sau
angày lại thực hiện hoạt động một lần. - Bạn B cứ sau
bngày lại thực hiện hoạt động một lần.
Biết rằng hôm nay hai bạn vừa cùng thực hiện hoạt động đó. Hãy xác định sau ít nhất bao nhiêu ngày nữa thì hai bạn lại cùng thực hiện hoạt động vào cùng một ngày.
Dữ liệu vào
Gồm một dòng chứa hai số nguyên dương a, b.
Dữ liệu ra
In ra số ngày ít nhất để hai bạn lại gặp nhau.
Ràng buộc
1 <= a, b <= 10^12
Ví dụ
Input
8 10
Output
40
Giải thích
Hai bạn sẽ gặp lại nhau sau BCNN(8, 10) = 40 ngày.
Bài 7. Chia hình chữ nhật thành các hình vuông lớn nhất
Mô tả
Cho một hình chữ nhật có chiều dài a và chiều rộng b (đơn vị mét).
Người ta muốn chia hình chữ nhật này thành các hình vuông bằng nhau sao cho cạnh của mỗi hình vuông là lớn nhất có thể.
Hãy xác định độ dài cạnh lớn nhất đó.
Dữ liệu vào
Gồm một dòng chứa hai số nguyên dương a, b.
Dữ liệu ra
In ra độ dài cạnh lớn nhất của hình vuông.
Ràng buộc
1 <= a, b <= 10^12
Ví dụ
Input
52 36
Output
4
Giải thích
Độ dài cạnh lớn nhất chính là UCLN(52, 36) = 4.
Bài 8. Chia đều vào nhiều đĩa nhất
Mô tả
Có k loại đồ vật, loại thứ i có a[i] món.
Người ta muốn chia tất cả các món đồ vào nhiều đĩa nhất sao cho:
- số món của từng loại được chia đều vào các đĩa;
- mỗi đĩa nhận cùng số món của từng loại.
Hãy xác định:
- số đĩa nhiều nhất có thể chia;
- số món của từng loại trên mỗi đĩa.
Dữ liệu vào
- Dòng 1 chứa số nguyên dương
k. - Dòng 2 chứa
ksố nguyên dươnga1, a2, ..., ak.
Dữ liệu ra
- Dòng 1 in ra số đĩa nhiều nhất.
- Dòng 2 in ra
ksố nguyên, số thứilà số món loạiitrên mỗi đĩa.
Ràng buộc
1 <= k <= 201 <= a[i] <= 10^12
Ví dụ
Input
3
80 48 64
Output
16
5 3 4
Giải thích
Số đĩa nhiều nhất là UCLN(80, 48, 64) = 16.
Bài 9. Chiều cao nhỏ nhất của các chồng sách
Mô tả
Có k chồng sách. Chồng thứ i gồm các cuốn sách cùng loại, mỗi cuốn dày a[i] milimét.
Người ta muốn xếp các chồng sách sao cho tất cả các chồng có cùng chiều cao và chiều cao đó là nhỏ nhất có thể.
Hãy tìm chiều cao nhỏ nhất đó.
Dữ liệu vào
- Dòng 1 chứa số nguyên dương
k. - Dòng 2 chứa
ksố nguyên dươnga1, a2, ..., ak.
Dữ liệu ra
In ra chiều cao nhỏ nhất của các chồng sách.
Ràng buộc
1 <= k <= 201 <= a[i] <= 10^9
Ví dụ
Input
3
15 6 8
Output
120
Giải thích
Chiều cao nhỏ nhất là BCNN(15, 6, 8) = 120.
Bài 10. Chia tổ học sinh
Mô tả
Một lớp học có a học sinh nam và b học sinh nữ.
Người ta muốn chia đều học sinh thành các tổ sao cho:
- số nam trong các tổ bằng nhau;
- số nữ trong các tổ bằng nhau;
- số tổ lớn hơn
1.
Hãy xác định:
- có bao nhiêu cách chia tổ;
- trong tất cả các cách chia hợp lệ, cách chia nào cho số học sinh trong mỗi tổ là ít nhất.
Dữ liệu vào
Gồm một dòng chứa hai số nguyên dương a, b.
Dữ liệu ra
In ra hai số nguyên:
- số cách chia tổ;
- số học sinh ít nhất trong mỗi tổ theo một cách chia hợp lệ.
Ràng buộc
1 <= a, b <= 10^12
Ví dụ
Input
28 24
Output
2 13
Giải thích
UCLN(28, 24) = 4 nên số tổ có thể chia là các ước của 4 lớn hơn 1, tức là 2 và 4.
Có 2 cách chia.
Để mỗi tổ có ít học sinh nhất, cần chia thành nhiều tổ nhất, tức là 4 tổ.
Khi đó mỗi tổ có (28 + 24) / 4 = 13 học sinh.