Question

c++大整数求余数

给定一个大整数，a[1000],求他对于一个整数b,的模，最好是直接写个函数，然后稍微给菜鸟我注释一下，谢谢

Answer 1

//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
char *amodb(char *a,char *b){
int i,j,la,lb=strlen(b);
while((la=strlen(a))>lb || la==lb && strcmp(a,b)>=0){
for(i=la-1,j=lb-1;j>=0;a[i--]-=(b[j--]-'0'));
for(i=la-1;i>0;i--)
if(a[i]<'0'){
a[i]+=10;
a[i-1]--;
}
while(*a=='0') a++;
}
return a;
}
void main(void){
char a[]="123452346156",x[15],*p;
int b=123456;
p=amodb(a,itoa(b,x,10));
printf("The result is %s.\n",*p ? p : "0");
}
原理是用大数减法计算a[1000]-b，一直减到结果小于b，则结果就是所求。

追问

是很大的数哦，这样减太慢了，要等很久，有没有别的算法

追答

我也还没有想出好办法。用同余定理，结果中间数仍然太大而不能正确表达……不过，若b不是大数的话，给你提供一个供参考：
int xmody(char *x,int y){
int i,m;
for(m=i=0;x[i];i++)
m=((m*10)%y+(x[i]-'0')%y)%y;
return m;
}
void main(void){
char a[]="123452346156";
int b=123456;
printf("The result is %d.\n",xmody(a,b));
}

追问

能不能解释一下从高位到低位的算法m=((m*10)%y+(x[i]-'0')%y)%y;？

追答

同余定理告诉我们：
(a+b)%c=(a%c+b%c)%c；
(a*b)%c=(a%c*b%c)%c。
设：大数串为12345，把它看成(((0x10+1)x10+2)x10+3)x10...因为1、2、3...是字符串且用x数组表示，所以变成(((0x10+x[0]-'0')x10+x[1]-'0')x10+x[2]-'0')x10...把这放在循环里，且m初值是0，以后用乘以10的权后累加，就是m=((m*10)%c+(x[i]-'0')%c)%c这样了。其中c是模。

Answer 2

#include<iostream>
using namespace std;
int main()
{
int a[1000], len = 999, b, t = 0;
while ( len > 0 && a[len] != 0 ) len--;
for (int i = len; i >= 0; --i)
{
t = t * 10 + a[i]; //t为当前余数
t = t % b;
}
cout << t << endl;
return 0;
}

例如 125/6
125=((1)*10+2)*10+5
在每个括号内取一次模，这样就可以从高位向低位枚举了
可以直接模拟一下这个过程~

追问

..真心没看懂，求讲解原理

追答

几天没来，上面的被采纳回答说得好偏，还是补充一下吧，以便让后来的同学看到。
同余定理不是这样的，这里只是用到了同余的一个基本性质，一般数论书的第一节就会介绍：
a mod b = c
b mod b = e
两式可以相加得到：
(a+b) mod b = (c+d) mod b
回到这个问题，简化地考虑三位数abc，则：
abc=a*100+b*10+c
abc mod 10 = (a*100+b*10+c) mod 10 = ((a*10+b)*10+c) mod 10
然后用上面的基本公式，每一步运算均模10处理。
for循环就是从高位到低位操作，每次把当前余数乘以10，再加上当前位（也即从abc mod 10那个式子的最里的括号，一直运算到最外的括号）。

可以百度“高精度运算”获得更多内容。