HSPC14A - Biến đổi cặp số
Bài toán này , để đơn giản , ta sẽ làm ngược bài toán :
từ 2 số (a,b) sử dụng các thao tác:
+(a , a-b) (nếu a>b)
+ (b, b-a) (nếu b>a)
sao cho đưa về trạng thái (1,1)
nhận thấy đấy chính là thao tác tìm UCLN của 2 số
Do số test nhỏ <= 10 nên ta có giải thuật đơn giản sau:
+ với mỗi số X , ta cần tìm Y để sao cho số UCLN (X,Y) = 1 và số bước tìm UCLN min
+ Giờ đây ta có hàm F(x,y) là số bước đưa số X,Y về trạng thái (1,1) --> F(x,y) == F(y%x, x) + y/x;
( với y>=x)
Dưới đây là code của mình : http://ideone.com/zDKK0N
