題目連結:
題目大意:
這題的強化版,現在 N 可以高達 1000000000000000 。
範例輸入:
T 5
T 4
F 10
F 22
T 10000
F 15751
T 1000000000000000
範例輸出:
6
5
9
20
15751
10000
5873731811138871
解題思維:
上一次的做法在這裡是行不通的( N 太大了)。因此我們需要引進一個類似但是稍有不同的想法。
因為不會用到「4」這個數字,就表示 0 ~ 9 只有 9 個數字被用到。而每一位數都是由「4」以外的 9 個數字組成,那不就是「九進位」嗎?
又因為是九進位,我們可以套用我們以前有的經驗去將數字轉換。在做進位制轉換時,要特別跳過「4」。以 0、1、2、3、5、6、7、8、9 作為「九進位」的九個符號,就像我們從沒發明「4」這個數字一樣。
而「T」代表要把給定的數字轉成這種「九進位」(少了「4」的 0 ~ 9 ),「F」則是代表把一個「九進位」數字轉成我們一般的十進位數字。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。