切換
舊版
前往
大廳
主題

ZeroJudge - b133: NOIP2006 4.數列 解題心得

Not In My Back Yard | 2019-02-27 12:30:48 | 巴幣 0 | 人氣 138

題目連結:


題目大意:
給定兩正整數 k 、 N (3 ≦ k ≦ 15 , 10 ≦ N ≦ 1, 000),代表有一數列是以某些 k 的次方項組成一個嚴格遞增的數列,如 k = 3 時會有:
3 ^ 03 ^ 13 ^ 0 + 3 ^ 13 ^ 23 ^ 0 + 3 ^ 2 ……
也就是
10 ……

以 k 作為這數列的基準,求第 N 項之值。



範例輸入:
3 100


範例輸出:
981


解題思維:
我們可以看到遞增的規律,也就是挑選的k之次方項的規律,剛好是二進位的 1 以公差為 1 慢慢增長。其二進位表示法當中的 1 即是代表要挑取的次方項。

例如: 10110 即代表要選 k ^ 4 、 k ^ 2 、 k ^ 1 。而此時的N值即為 10110 ,也就是 22 。所以我們只要將給定的 N ,從原本的十進位轉成二進位表示,再把相應的 k 之次方(二進位有 1 的位數)全部加總,便可達成所需。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作