b573. 排列組合、最大公因數
Tags :
Accepted rate : 124人/133人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-09-30 23:41

Content

全國高級中等學校,102學年度,商業類科學生技藝競賽,程式設計-正式題P22

排列組合、最大公因數。(程式執行限制時間: 3 秒) 改為 1
最大公因數(Greatest Common Divisor,簡寫為G.C.D.),指某幾個整數共有因數中最大的一個。
在排列組合問題中將一組數字進行排列,可以得到不同的數字順序,例如12 這個數的排列共有:(1)12、(2)21 二組(由小到排序);例如123 這個數的排列組合順序為:(1)123、(2)132、(3)213、(4)231、(5)312、(6)321 六組(由小到排序);例如1234 這數的排列組合有24 組,數列順序如下:
(1)1234     (2)1243     (3)1324     (4)1342     (5)1423     (6)1432
(7)2134     (8)2143     (9)2314    (10)2341    (11)2413   (12)2431
(13)3124   (14)3142   (15)3214   (16)3241    (17)3412   (18)3421
(19)4123   (20)4132   (21)4213   (22)4231   (23)4312    (24)4321

Input

 第 1 列的數字n 代表有幾筆資料要測試,2<=n<=5 ,之後每列為每筆的測試資料,共有三個正整數i,j,k中間空白隔開。

 以i 這值進行排列組合,i 的集合為{12,123,1234,12345,123456},再依i 值排列組合順序(由小到大排序),找出第j 個和第k 個的值,再算出個這二個值的最大公因數。第j個和第k 個的值會存在以i 值排列組合數列中。
 例如i,j,k:12,1,2 這組測試資料中,12 這個數的排列組合有:(1)12、(2)21 二組(由小到大排序),第1 個值為12;第2 個值為21;GCD(12,21)=3。
 例如i,j,k:123,2,5這組測試資料中,123 這個數的排列組合有:(1)123、(2)132、(3)213、(4)231、(5)312、(6)321 六組(由小到大排序),第2 個值為132;第5 個值為312;GCD(132,312)=12。
 例如i,j,k:1234,5,9這組測試資料中,1234 這個數的排列組合有24 組(由小到大排序),第15 個值為3214;第9 個值為2314;GCD(3214,2314)=2。
例如i,j,k:1234,3,4這組測試資料中,1234 這個數的排列組合有24 組(由小到大排序),第3個值為1324;第4 個值為1342;GCD(1324,1342)=2。
例如i,j,k:1234,2,5這組測試資料中,1234 這個數的排列組合有24 組(由小到大排序),第2個值為1243;第5 個值為1423;GCD(1243,1423)=1。

Output

每筆測試資料輸出一列。輸出以i 值排列組合順序中,找出第j 個和第k 個的值,再算出個這二個值的最大公因數。

Sample Input #1
5
12 1 2
123 2 5
1234 15 9
1234 3 4
1234 2 5
Sample Output #1
3
12
2
2
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1K
公開 測資點#3 (25%): 1.0s , <1K
Hint :

因測資有誤,感謝 310573sao 指出,已修正,抱歉!

Tags:
出處:
102學年度商業類程式設計競賽 [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」