大數問題。C語言中沒有大整數類型，當一個數超過long long時我們就沒辦法直接表示，只能通過數組模擬（字符數組，或者整形數組），與Java相比，這一點真是夠折磨人的，記得今年省賽的時候，有一題是關于大數的，有人直接用Java中的BigInteger類，很輕松的就搞定了，C語言真是無法望其項背。這里我們用C解一道大數乘法題，
其實模擬大數運算就是在模擬小學生算算術，這一題只牽涉到了加法和乘法，我就說著兩種操作。
加法Add()：1.對位，將權值相同的各位對其
2.相加，將相應的每一位相加
3.進位，從低位到高位依次進位
乘法：a*b乘法是在加法的基礎上完成的，跟我們手算乘法的過程一樣，依次將b的每一位與a相乘，加到一起就行了。需要注意的是b中的每一位權值是不一樣的。
為了對位方便，我們通常是將數字倒置過來，即低位在左邊，高位在右邊。字符串處理都是些細節，不小心就會犯錯誤。
以下是poj3167的代碼：
題意：給兩個數K、M，求n，使得M^n的第K為是數字7。
#include<stdio.h>
#include<stdlib.h>//zoj3167
#define LEN 310
void Add(int *A, int *B)//A[]=A[]+B[]
{
int i, j;
for(i = 0; i < LEN; i++)
{
A[i] += B[i];
}
int t = 0;
for(i = 0; i < LEN; i++)
{
int t1 = (A[i] + t) / 10;
A[i] = (A[i] + t) % 10;
t = t1;
}
}
void MultiOne(int *B, int i, int w)//B[]*(i*10^(w-1))
{
int j, k;
for(j = LEN - 1; j >= w - 1; j--)
B[j] = B[j - w + 1];
for(k = 0; k < w - 1; k++)
B[k] = 0;
for(j = 0; j < LEN; j++)
B[j] *= i;
int t = 0;
for(i = 0; i < LEN; i++)
{
int t1 = (B[i] + t) / 10;
B[i] = (B[i] + t) % 10;
t = t1;
}
}
void Set0(int *A)
{
for(int i = 0; i < LEN; i++)
A[i] = 0;
}
void Copy(int *F, int *T)
{
int i;
for(i = 0; i < LEN; i++)
T[i] = F[i];
}
int main()
{
int i, j;
int K, M;
int A[LEN];//存儲M^t，這是當前乘方計算的結果
int B[LEN];//B[]和C[]一起完成對M^(t+1)的計算，B[]存儲M^t與b的某一位i相乘的結果，
int C[LEN];//C[]用來存儲計算到b的當前位時的累加結果
while(scanf("%d%d", &K, &M) != EOF)
{
int n = 1;
Set0(A);
Set0(B);
Set0(C);
int t = M;
for(i = 0; t > 0; i++)//init A as M^1
{
A[i] = t % 10;
t /= 10;
}
while(A[K - 1] != 7)
{
Set0(C);
int t = M;
int w = 1;
while(t > 0)
{
Copy(A, B);
int ii = t % 10;
MultiOne(B, ii, w);
Add(C, B);//每一次算完B[]，累加到C[]上
w++;
t /= 10;
}
Copy(C, A);
n++;
}
printf("%d\n", n);
}
//system("pause");
}posted on 2012-08-04 09:31
小鼠標 閱讀(1193)
評論(0) 編輯 收藏 引用 所屬分類:
大數