大数模运算(JSU-ZJJ)

柔光的暖阳◎ 2022-04-03 02:30 164阅读 0赞

###  ###

题目描述

给定任意位数长度的两个整数，求第一个整数对第二整数的模数。

输入

每个测试用例含有两个整数，代表两个任意位数长度的整数A，B。

输出

计算出这两个任意位数长度的整数的模数。

样例输入

50000000000 3  
12 6

样例输出

2  
0

##### 分析： #####

本题的基本思路是不断做减法，直到不能减为止。不过，在做减法的时候也是有一定讲究的。例如：9999 MOD 11 那么我们可以先将11扩大至1100 在做减法。直到不能减为止。就在将其1100变成110 在做减法，直到不能减。然后变成11，直到不能减。基本思路是如此。不过，代码实现却也是比较困难的。

#include"stdio.h"
    #include"string.h"
    //将一个字符串前后置换位置。方便做减法
    void exchange(char string[],int leght)
    {
    
        int i,j;
        char t;
        j=leght-1;
        i=0;
        while(i<j)
        {
            t=string[i];string[i]=string[j];string[j]=t;
            i++;
            j--;
        }
    }
    int leght;
    //减法 
    int subtract(char stringA[],int leghtA,char stringB[],int leghtB)
    {
    
        int i,j;
        //如果B的长度小于原始字符串B的长度，则要将其换成原始的。
        if(leghtB<leght)
            leghtB=leght;
        leghtA=strlen(stringA);
       // printf("subtract.leghtA=%d\n",leghtA);
       // printf("subtract.leghtB=%d\n",leghtB);
        stringB[leghtB]='\0';
        //如果字符串A的长度比B小，就可以直接返回-1了。
        if(leghtA<leghtB)
             return -1;
        else
        //这里是判断一下字符串A到底能不能减去字符串B 
            if(leghtA==leghtB)
             {
                   for(i=0;i<leghtA;i++)
                        if(stringA[i]<stringB[i])
                           return -1;
                         else
                            if(stringA[i]>stringB[i])
                                break;
    
             }
             //置换位置，方便做减法
        exchange(stringA,leghtA);
        exchange(stringB,leghtB);
        //这里是减去过程，但未进位。
        for(i=0;i<leghtA&&i<leghtB;i++)
        {
            stringA[i]=stringA[i]-stringB[i]+'0';
        }
        //如果A中有高位未能执行，则要将高位的先赋值到A中
        while(i<leghtA)
            stringA[i]=stringA[i++];
            //这里是进位过程。
        for(i=0;i<leghtA;i++)
            if(stringA[i]<'0')
                {stringA[i]+=10;
                 stringA[i+1]--;
                }
        while(leghtA)
            if(stringA[leghtA-1]!='0')
                break;
            else
                leghtA--;
        stringA[leghtA]='\0';
        //置换回来
        exchange(stringA,leghtA);
        exchange(stringB,leghtB);
       // printf("Sub.stringA=%s\n",stringA);
        //printf("Sub.stringB=%s\n",stringB);
       // getch();
      return leghtA;
    }
    int main()
    {
        char stringA[10000],stringB[10000];
        int leghtA,leghtB,new,L;
        int i,j;
        while(~scanf("%s%s",stringA,stringB))
        {
            leghtA=strlen(stringA);
            leghtB=strlen(stringB);
            leght=leghtB;
            if(leghtA<leghtB)
            {
                printf("%s\n",stringA);
                continue;
            }
            for(i=leghtB;i<leghtA;i++)
                 stringB[i]='0';
            stringB[i]='\0';
           // printf("main.stringA=%s\n",stringA);
           // printf("main.stringB=%s\n",stringB);
            leghtB=leghtA;
            L=leghtA;
            for(i=0;i<L;i++)
            {
                while((new=subtract(stringA,leghtA,stringB,leghtB-i))!=-1);
                //leghtB=leghtA;
            //  stringB[leghtB-i]='\0';
              //leghtB=strlen(stringB);
            //  printf("MAIN.stringA=%s\n",stringA);
           //   printf("MAIN.stringB=%s\n",stringB);
              leghtA=strlen(stringA);
                if(leghtA==leght)
                {
                     for(j=0;j<leghtA;j++)
                        if(stringA[j]<stringB[j])
                           break;
    
                }
    
    
            }
      // printf("i=%d \n",i);
        if(strlen(stringA)!=0)
            printf("%s\n",stringA);
        else
            printf("0\n");
       // printf("main.leghtA=%d\n",leghtA);
       // printf("main.leghtB=%d\n\n",leghtB);
        }
    }