大数问题。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
小鼠标 阅读(1157)
评论(0) 编辑 收藏 引用 所属分类:
大数