切換
舊版
前往
大廳
主題

ZeroJudge - e612: 13178 - Is it multiple of 3?　解題心得

Not In My Back Yard | 2020-01-20 00:31:34 | 巴幣 0 | 人氣 263
題目連結：
題目大意：
給定一正整數 T ，代表有 T 筆測試資料，每筆佔一列。每列給定一正整數 n （1 ≦ n ≦ 10 ^ 9），代表會升成一個數字為 1 ～ n 連在一起。例如 n ＝ 2 ，則升成出 12 ；n ＝ 10 ，則會是 12345678910 等等。

試問生成的數字可否被 3 整除？

範例輸入：
3
2
6
130000000
範例輸出：
YES
YES
NO
解題思維：
已知判斷一數是否為 3 的倍數，。若且唯若其位數和（例 1235 的位數和為 1 ＋ 2 ＋ 3 ＋ 5 ＝ 11）為 3 的倍數。要判斷位數和是否可被 3 整除可以再次套用相同的方式。

因此，如果 n 為 3 的倍數則生出來的數必為 3 的倍數。

因為 1 的位數和 ＋ 2 的位數和 ＋ 3 的位數和 ＋ 4 的位數和 ＋ 5 的位數和 ＋ 6 的位數和 ＋ …… ＋ n 的位數和為 3 的倍數，若且唯若 n 不為 3 的某倍數 － 1 （1 與 2 、 4 與 5 、……的位數和會彼此合為 3 的倍數，所以如果級數停在 3 的倍數 － 1 則沒有下一個數字可以與之合為 3 的倍數）。

所以只要判斷 n 取 3 的餘數是否為 1 即可。如果是，則代表生成的數字不會是 3 的倍數；反之，代表生成數為 3 的倍數。

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

創作回應

追蹤 創作集

作者相關創作

作品資料夾

來層愛透不透的性感

看更多

相關創作

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

更多創作

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