主題
題目連結：
題目意譯：
你被給定兩正整數 n 和 target。
如果一整數其每一位數和小於等於 target，則將會被視為美麗的。
回傳最小非負整數 x，使得 n + x 是美麗的。輸入之生成滿足永遠可以讓 n 變成美麗的。
限制：
1 ≦ n ≦ 10 ^ 12
1 ≦ target ≦ 150
輸入之生成滿足 n 一定可以變成美麗的。
範例測資：
範例 1：
輸入： n = 16, target = 6
輸出： 4
解釋： 一開始 n = 16 而其位數和為 1 + 6 = 7。在加上 4 之後，n 變為 20 而其位數和為 2 + 0 = 2。可以證明我們沒辦法加上小於 4 的非負整數來使 n 變成美麗的。
範例 2：
輸入： n = 467, target = 6
輸出： 33
解釋： 一開始 n = 467 而其位數和為 4 + 6 + 7 = 17。在加上 33 之後，n 變為 500 而其位數和為 5 + 0 + 0 = 5 + 0 + 0。可以證明我們沒辦法加上小於 33 的非負整數來使 n 變成美麗的。
範例 3：
輸入： n = 1, target = 1
輸出： 0
解釋： 一開始 n 為 1，而其位數和為 1，其值已經小於等於 target。
解題思維：
可以看到如果我們每次都把 n 之中最低位（也就是最靠右）的「非零」數字加到進位，例如 4670 最低位是 7（位數和 17），而我們加 30 使其變成 4700（位數和 11）。
而這個操作將會把位數和減去 (x - 1)，其中 x 為最低位數字之值。因此可以看到只要我們一直找非零的最低位數字並做以上操作，位數和之值就會減少或是維持不變，最終抵達 1。
而同時這個重複這個操作會是最佳的策略。可以用反證法證明，不過情況有點多，故在此省略。
注：證明核心基本上就是假設存在一組最佳解一開始不是取最低位的，然後你便試著用最低位把它換成有對最低位做出操作。接著會發現位數和一樣小於等於 target 且比原本的最佳解的數字還小，因而產生矛盾。而這邊就是需要討論各種情況的部分了（替換之後可能會進位也可能不會，被替換的也可能有進位所以要把位數和加回去等等等情況不少）。
因此我們就重複上述定義的操作，直到位數和小於等於 target 為止。然後把每次操作中加上的數字加總即為所求。
不過程式碼中並不完全是上述的操作，因為看到是「零」的位數時依舊會使其進位，也就是說位數和可能會先上升。至於為何這樣不會出問題，就留給讀者思考。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
