[C++知识库]高精度取余

同余定理的应用

1 （a+b)%m=(a%m+b%m)%m;

2 (a*b)%m=((a%m)*(b%m))%m;

高精度取余是将数看成各位数的权值与个位数乘积的和。

利用上面定理模拟的

如456=（（4*10）+5)*10+6;

1? ? ?类如456%4

过程为 4%4=0，（0*10+5)%4=1,(1*10+6)%4=0;

代码如下：

# include <stdio.h>
# include <string.h>
int main()
{
?? ?int b;
?? ?char s[1000];
?? ?scanf("%s",s);
?? ?scanf("%d",&b);
?? ?int n=strlen(s);
?? ?int d=1;
?? ?for(int i=1;i<n;i++)
?? ?{
?? ??? ?d=(d*10+s[i]-'0')%b;?
?? ?}
?? ?printf("%d",d);
?? ?
?}?