用python或是java這種支援大數運算的很簡單 但我們今天要討論如何用c/c++解題
想想3的倍數是如何判斷的，把每個位數相加，如果是3的倍數，該數就是3的倍數
但背後的原理是甚麼?
12345可以看成1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 1
我們要計算12345 mod 3是否等於0就等於在問1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 1 mod 3 有沒有 = 0
這時候我們可以運用同餘的特性簡化算式：1 * (9 + 1)^4 + 2 * (9 + 1)^3 + 3 * (9 + 1)^2 + 4 * (9 + 1)^1 + 5 * 1
=> 1 * (0 + 1)^4 + 2 * (0 + 1)^3 + 3 * (0 + 1)^2 + 4 * (0 + 1)^1 + 5 * (0 + 1) = 1 + 2 + 3 + 4 + 5
會發現很多9..的那邊會因為同餘3被削去，因此只剩下每個位數相加是不是3的倍數要判斷
那要怎麼把這個原理套用到81呢？
首先，要先知道1000000000(10^9) mod 81 = 1(用計算機按出來的)
接下來就可以把剛剛的原理把套用到這題上
1234567890987654321 = 1 * 1000000000^2 + 234567890 * 1000000000^1 + 987654321 mod 81 = ?
運用同餘：1 * (... + 1)^2 + 234567890 * (... + 1)^1 + 987654321 mod 81 = ?
=> 1 + 234567890 + 987654321 mod 81 = ?
可以發現就是每九數字相加判斷是不是81的倍數
用python或是java這種支援大數運算的很簡單 但我們今天要討論如何用c/c++解題
想想3的倍數是如何判斷的，把每個位數相加，如果是3的倍數，該數就是3的倍數
但背後的原理是甚麼?
12345可以看成1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 1
我們要計算12345 mod 3是否等於0就等於在問1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 1 mod 3 有沒有 = 0
這時候我們可以運用同餘的特性簡化算式：1 * (9 + 1)^4 + 2 * (9 + 1)^3 + 3 * (9 + 1)^2 + 4 * (9 + 1)^1 + 5 * 1
=> 1 * (0 + 1)^4 + 2 * (0 + 1)^3 + 3 * (0 + 1)^2 + 4 * (0 + 1)^1 + 5 * (0 + 1) = 1 + 2 + 3 + 4 + 5
會發現很多9..的那邊會因為同餘3被削去，因此只剩下每個位數相加是不是3的倍數要判斷
那要怎麼把這個原理套用到81呢？
首先，要先知道1000000000(10^9) mod 81 = 1(用計算機按出來的)
接下來就可以把剛剛的原理把套用到這題上
1234567890987654321 = 1 * 1000000000^2 + 234567890 * 1000000000^1 + 987654321 mod 81 = ?
運用同餘：1 * (... + 1)^2 + 234567890 * (... + 1)^1 + 987654321 mod 81 = ?
=> 1 + 234567890 + 987654321 mod 81 = ?
可以發現就是每九數字相加判斷是不是81的倍數
首先謝謝版主分享解法
我是從頭開始除 除到尾看餘數 畢竟要知道10^9 mod 81 = 1好像有點通靈成分...