切換
舊版
前往
大廳
主題

ZeroJudge - e590: 11371 - Number Theory for Newbies　解題心得

Not In My Back Yard | 2020-01-25 21:56:07 | 巴幣 2 | 人氣 122
題目連結：
題目大意：
已知給定任意正整數 n ，將其位數打散重組成另一數。該數與 n 之差必為 9 的倍數。

輸入有多筆測試資料，每筆佔一列。每列給定一正整數 n （n ≦ 2000000000），請找到一組數對 a 、 b （兩數由 n 重組而得且兩者皆無前導 0），其差值（a － b）盡可能地大，並找出該差值可由 9 乘以何數而得。

輸出格式請參見範例輸出。

範例輸入：
123
2468
範例輸出：
321 - 123 = 198 = 9 * 22
8642 - 2468 = 6174 = 9 * 686
解題思維：
要讓差值盡量地大，也就是要讓 a 盡量地大、 b 盡量地小。

明顯可以看出將 n 的各個位數由大排到小，即可得最大的數字；而最小，因為不能有前導 0（即不能以 0 開頭），所以將位數由小到大排的時候，將 0 的順位放在第二順位（n 有 1 就放排在 1 之後、沒有 1 就排在 2 之後、沒有 2 就排在 3 之後等等）。

分別排完得到兩數之後就單純地相減可。但是如果是用 C 、 C++ 等需要使用 long long 型態來儲存 a 、 b 。因為 n 重新排列之後可能會超出 int （2 ^ 31 - 1）範疇。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#數論
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

相關創作

鳥鳥玩數學-有趣的擲骰子機率問題(2022 大阪大學前期)
0 196
鳥鳥玩數學-高斯符號找質因數個數及原理(2020-2021 Hồ Chí Minh，Vietnam)
1 295
鳥鳥玩數學-平方差整數解之小技巧
1 266
鳥鳥玩數學-2022年考生要注意的事
0 313
鳥鳥玩數學-分母為相異質數不定方程(2016 越南數學選拔)
1 254
鳥鳥玩數學-對數與數論結合方程組問題(2019 AIME I)
0 326
鳥鳥玩數學-1000! 1000!! 999!! 找質因數個數(2018大阪市立大學)
0 210
鳥鳥玩數學-經典數論名題133^5+110^5+84^5+27^5=n^5 (1989 AIME)
0 296
鳥鳥玩數學-解 2^x+2^y+2^z=2336 (1982 Vietnam Mathematical Olympic)
0 228
鳥鳥玩數學-數論與平面座標的結合(2020 北海道大學 前期)
0 171
鳥鳥玩數學 三角函數與對數的結合(2019 京都大學前期)
0 261
鳥鳥玩數學-為兩年後準備，sqrt(a)+sqrt(b)=2023 正整數解
1 318
鳥玩數學-與2015互質，第2015個數(104高雄市聯招)
0 218
鳥鳥玩數學-證明sin1 cos1 tan1為無理數
0 301
鳥鳥玩數學-餘弦定理意想不到的用法，質數與餘弦定理的組合
0 275
鳥鳥玩數學-什麼!! n個相異自然數和等於n個相異自然數積只有一組解(1977 岐阜大學)
0 174
達人 《憂國的莫里亞蒂》中的數學公式
68 3185
cf #460 (Div. 2) pE Congruence Equation
0 140

更多創作

追蹤 創作集
其他創作
作品資料夾