ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - d364: 10637 - Coprimes 解題心得

Not In My Back Yard | 2019-01-28 23:02:07 | 巴幣 0 | 人氣 310

題目連結:


題目大意:
第一列給定一正整數 N (N < 40),代表接下來有N列輸入。

每列輸入給定兩正整數 S 、 t (0 < S ≦ 100 , 0 < t ≦ 30),代表要把S分成t個彼此互質(彼此的最大公因數為 1 )的正整數。

請窮舉出所有可能的方法,每一個方法的那 t 個數字要由小到大排。而不同的方法之間要照類似字典序的順序輸出(先比第一個數字,再比第二、第三……小的在要放在前面輸出)。見範例輸出。



範例輸入:
4
40 6
8 3
5 2
3 1



範例輸出:
Case 1:
1 1 1 1 1 35
1 1 1 1 5 31
1 1 1 1 7 29
1 1 1 1 11 25
1 1 1 1 13 23
1 1 1 1 17 19
1 1 1 3 5 29
1 1 1 3 11 23
1 1 1 5 9 23
1 1 1 5 11 21
1 1 1 5 13 19
1 1 1 7 11 19
1 1 1 7 13 17
1 1 1 9 11 17
1 1 3 5 7 23
1 1 3 5 11 19
1 1 3 5 13 17
1 1 3 7 11 17
1 1 5 7 9 17
1 1 5 9 11 13
1 3 5 7 11 13
Case 2:
1 1 6
1 2 5
1 3 4
Case 3:
1 4
2 3
Case 4:
3



解題思維:
整數分拆的題目類似,每一個格子都先放放看可以放的數字。數字從 1 開始判斷,這樣才可以保證數字由小到大,並判斷是否與之前的數字互質。

但是每一個格子不是從 1 跑到 S ,而是跑到「目前剩餘要湊的數字 ÷ 目前的所剩的格子數」。這樣既保證不會破壞由小到大的排列,也不會跑到一些不可能的情況。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作