切換
舊版
前往
大廳
主題

ZeroJudge - b546: 2.特殊數列 解題心得

Not In My Back Yard | 2020-10-03 00:01:11 | 巴幣 0 | 人氣 144

題目連結:


題目大意:
輸入有多列。每列給定兩正整數 a 、 n (1 ≦ a 、 n ≦ 100),代表一個數列 V 的首項,要求第 n 項的值。

數列 V 的每一項 Vi 為以下方式計算:
V1 = a;
Vi = Vi-1 × (i - 1) ,如果 Vi 可以被 (i - 1) 整除;
Vi = Vi-1 ÷ (i - 1) ,如果 Vi 不能被 (i - 1) 整除;



範例輸入:
2 6
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 15
3 20
4 30
5 55


範例輸出:
60
1
2
6
24
120
20
140
1120
10080
429
99768240
2617608150
5408716924823454000


解題思維:
就是單純地照做算到第 n 項即可。

而過程會使用大數運算,因此詳見大數乘法的做法。

除法以及取餘數也是類似的想法,以下講述除法:
將一個很長的整數拆分成好幾個區塊,從最高位開始往下除。

對於每一塊,用一個變數存上一個計算區域除完後的餘數 R。將此區域的值加上 R × 單一區塊大小(如果一塊可以存 b 位數,則即是乘以 10 ^ b),然後除以除數,並取得下一塊要用的 R 之餘數值。




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

創作回應

更多創作