高精度取余

高精度取余

同余定理的应用

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
# include
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     {
        d=(d*10+s[i]-'0')%b; 
    }
    printf("%d",d);
    
 }