一個特別大的數除以23求餘數用C語言應該怎麼算啊？比如23232323232323232323232323232323232323232323232323232323233除以23，怎麼算餘數？

@PhTirst 給出的建議是自己實現一個大整數計算。有一說一，這個題真的不需要你自己實現大數計算。這題考察的有窮狀態自動機。

當年我師父（教 C 語言和編譯原理以及演算法競賽的）在訓練時提了一個「大整數對 3 取模的餘數是多少」的問題。很多人的直接反應都是直接看各位相加對 3 的餘數。實際上，這個做法不具有可延展性。

我師父帶我們看了一個不一樣的解題視角：既然是模 3，那就只有 3 種狀態，即餘 0 的、餘 1 的和餘 2 的。然後輸入也只有 10 種可能，所以只要看在當前的狀態下，輸入下一個字元，會跳轉到什麼狀態就行了。

當年我就是我們學校 OJ 開發和管理組的成員。所以後來我就把原來的問題稍作擴充在 OJ 上出了一道新題，問 16 進位的大數取模的。你這題雖然數字不同，但本質都一樣。所以看到這題，2333。我甚至有點懷疑你是我母校的學弟。當然是不是我目前還不知道。不過至少從你的上一個被關閉的提問可以看到，這題肯定也是一個 ACMer 出的。

代碼如下：

#include &

using namespace std;

int main()
{
int table[10][23];

for (int i = 0; i &< 10; ++i) { table[i][0] = i; for (int j = 1; j &< 23; ++j) { table[i][j] = (table[i][j - 1] + 10) % 23; } } int c; int mod = 0; while ((c = getchar()) != EOF) { if (c == ) { printf("%d ", mod); mod = 0; } else { // c in 0...9 c -= 0; mod = table[c][mod]; } } return 0; }

時間複雜度是 O(n) 的，和輸入的大數的字元長度成線性，只要把字元串掃描一遍就能得到結果。空間複雜度 O(1)，連大數本身都不需要存儲。只需存三個內容：

  1. 當前狀態（即變數 m）。描述截止到當前輸入下，模數是多少。
  2. 輸入的下一個字元（即變數 c）。
  3. 狀態轉換表（即 table 數組）。描述在當前狀態下，輸入下一個字元後，跳轉到什麼狀態。

這就結束了，也就小三十行，沒那麼難~

如果有讀者不相信這份代碼的正確性大可以用 Python 去驗證~

按照 @O5-Paxol 的解釋

我把代碼寫出如下

#include "stdio.h"
#include "string.h"

int main()
{
int c;
int mod = 0;

/*如果沒有按下Ctrl+C 就一直在while循環裡面判斷*/
while ((c = getchar()) != EOF) {
if (c ==
) {/*輸出結果*/
printf("%d
", mod);
mod = 0;
} else {/*遞歸計算*/
// c in 0...9
c -= 0;
mod = mod +c;
mod = (mod*10)%3;
}
}
return 0;
}

程序輸出

weiqifa@bsp-ubuntu1804:~/c/dashuqiuyu$ gcc 1.c ./a.out
1
1
2
2
3
0
4
1
5
2
4564564564156189411651561561561561561
1

數論題，可以只用模運算解決，不僅時間複雜度是 [公式] ，空間複雜度還是 [公式] 。用大整數運算實屬殺雞用牛刀，還佔了一堆內存空間。

對於取模23，只需要：

  1. 聲明結果變數，假設它是 [公式] 。令 [公式] 作為起始條件。
  2. 取走最高位數碼，假設它是 [公式] ，令 [公式] 。
  3. 如果還有數碼沒有被取走，則令 [公式] ，並返回第2步

最終得到的 [公式]就是答案。具體代碼請自己完成。

下面是一個簡單的證明：

假設一個十進位數字abc，則它可以被展開成 [公式] 。形式化地，假設 [公式] 是數字 [公式] 第 [公式] 位數碼，則 [公式]

[公式] 還可以轉化為 [公式] 。觀察這個形式，可以發現其中蘊含了遞歸的過程。推而廣之，對任何一個十進位正整數，都可以表示成一系列乘10加 [公式] 的步驟。舉例：

[公式]

有了上面的形式，我們可以根據求餘公式：

  1. [公式]
  2. [公式]

所以：

[公式]

[公式]

[公式]

[公式]

你會發現這個過程可以無限套娃，對任意長的十進位數都適用。實際上如果模數比較友好，可以僅重複「乘10加t模p」到無數可加為止。至少本題的係數10讓23來模是白白模一次（ [公式] ），t讓23模也是白白算一次（ [公式] ），所以這些冗餘的計算不如都砍掉，只對積取一次模（也就是對每個輸入的數碼t，執行 [公式] ）。

推而廣之，k進位整數都可以用「乘k%p加t%p模p」的流程進行大整數取模。

原理別人都解釋過了。

有很多C語言大數運算庫，想自己寫就隨便找一個庫參考一下，不想自己寫就隨便找一個庫用。

這裡介紹一個簡單的大數庫，Morn基礎庫裏的一個小函數。用其解決此問題，可如下編碼：

#include "morn_math.h"
int main()
{
MLInt a,b;
int c;
mStringToLInt("23232323232323232323232323232323232323232323232323232323233",a);
mLIntDivS32(a,23,b,c);
printf("remainder=%d
",c);
return 0;
}

當然，你給的這個例子太過簡單，餘數顯然為3。

實際上大整數的除法是模擬豎式除法進行的，下面代碼摘自 除法豎式的原理是什麼？

#include& //大整數除以一位數的c++程序
using namespace std;

//求大整數除以一位整數的商和餘數(a,la)= k*(q,lq)+r;
int longDivInt(const int a[],int la,int k,int q[],int lq,int r);

//大整數存入數組，例s="1205"轉存a[0]=5,a[1]=0,...,a[3]=1,la=4
void storeStringToArr(string s,int a[],int la);

//輸出大整數
void outputArr(int a[],int la);

int main()
{
string s;
int a[1000],la,k,q[1000],lq,r; //數組a存放大整數的每一位數字，la存放大整數長度
cin&>&>s&>&>k; //輸入大整數s及不為零的一位數k
storeStringToArr(s,a,la); //以字元串輸入的大整數轉存到數組 (a,la)
longDivInt(a,la,k,q,lq,r);//大整數（a,la）= k*(q,lq)+r;
outputArr(q,lq); //輸出商
cout&=0;i--) //演算法核心：模擬除法過程
{
r=r*10+a[i]; //湊出目前要平分的數目（堆數）
q[i]=r/k; //完成本次平分
r=r%k; //算出本次剩餘，留待下次湊堆
}
if(q[la-1]==0) lq=la-1; else lq=la; //確定商的位數
}

void storeStringToArr(string s,int a[],int la) //例s="1205"轉存a[0]=5,a[1]=0,...,a[3]=1,la=4
{
la=s.size();
for(int i=0,j=la-1;i&=0;i--)cout&

運行程序，輸入一個1000位以內的大整數，以及9位以內的整數（因為k用int型），輸出是商及餘數。

寫個程序把自己列豎式算除法的過程模擬出來就行了。

隨便舉個例子，比如21903除以23。

  1. 被除數第一位，2 mod 23 = 2
  2. 被除數下一位， 2 * 10 + 1 = 21; 21 mod 23 = 21
  3. 被除數下一位， 21 * 10 + 9 = 219; 219 % 23 = 12
  4. 被除數下一位， 12 * 10 + 0 = 120; 120 % 23 = 5
  5. 被除數下一位， 5 * 10 + 3 = 53; 53 % 23 = 7

這個流程寫程序實現就很簡單了吧，不管被除數有多少位演算法也不會變。

初學者

可以讀到一個很長的字元串a【10000】，讀第一個字元減』0』轉int乘10加第二個字元減』0』轉int取3餘數，循環下一個字元減0再int取餘數直到最後一個數，用strlen，我認為應該可行（我都懷疑自己寫不寫得出）。

請大神指正。

————————————————————————————

最近剛寫了大數相加和相減，然後遇到相乘！

%

推薦閱讀：
相關文章