Nội dung Bài tập
- Mã:
- zGCD50
- Tên:
- GCD50
- Dạng thi:
- oi
- Thang điểm:
- 50 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phuc
Những số nguyên tố nhỏ hơn 50 được rất nhiều người quan tâm. Gọi tích của các số đó là M . Bài toán này liên quan đến các ước số của M. (M=2×3×5×7×11×13×17×19×23×29×31×37×41×43×47)
Ban đầu bạn được cho một số N (N là ước của M). Bạn được cho phép thực hiện Q thao tác có dạng x y (x, y là các ước số của M) với ý nghĩa là đổi số N lấy số [(N, x), y]. Mỗi thao tác có thể thực hiện nhiều lần. Bạn cần biến đổi sao cho số thu được là lớn nhất. Nhiệm vụ của bạn là in ra số lớn nhất này.
Input
• Dòng đầu chứa hai số nguyên dương N và Q, là số ban đầu và số lượng các thao tác được chophép (N là ước số của M, 1 ≤ Q ≤ 50).• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x, y, cho phép bạn thực hiện thao tác x y(x, y là các ước số của M).
Output
• Một dòng duy nhất chứa số lớn nhất có thể đạt được sau khi thực hiện các bước biến đổi.
Ví dụ:
Input Output 10 2 35 3 5 14105
Giải thích:10 → 70 (thao tác 5 14)70 → 105 (thao tác 35 3)
Lưu ý: Kí hiệu (x, y) là ước số chung lớn nhất của x và y, [x, y] là bội số chung nhỏ nhất của x và y.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...