PAT 大数运算

PAT中关于大数的有B1017,A1023,A1024 (A-Advance,B-Basic)

B1017

1017. A除以B (20)

本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。

输入格式：

输入在1行中依次给出A和B，中间以1空格分隔。

输出格式：

在1行中依次输出Q和R，中间以1空格分隔。

输入样例：

123456789050987654321 7

输出样例：

17636684150141093474 3

 #include <iostream>

 #include <cstring>

 using namespace std;

 const int N=;

 struct bignum{

     int d[N];

     int len;

     bignum(){

         memset(d,,sizeof(d));

         len=;

     }

 };

 bignum change(char str[]){

     bignum res;

     res.len=strlen(str);

     for(int i=;i<res.len;i++)

         res.d[i]=str[res.len--i]-'';

     return res;

 }

 bignum divide(bignum a,int b,int &r){

     bignum res;

     res.len=a.len;

     for(int i=res.len-;i>=;i--){

         r=r*+a.d[i];

         if(r<b)

             res.d[i]=;

         else{

             res.d[i]=r/b;

             r%=b;

         }

     }

     while(res.len> && res.d[res.len-]==)

         res.len--;

     return res;

 }

 void printbign(bignum t){

     for(int i=t.len-;i>=;i--)

         printf("%d",t.d[i]);

 }

 int main()

 {

     char A[N];

     int B;

     while(scanf("%s%d",A,&B)!=EOF){

         bignum a,q;

         int r=;

         a=change(A);

         q=divide(a,B,r);

         printbign(q);

         printf(" %d\n",r);

     }

     return ;

 }

A1023. Have Fun with Numbers (20)

http://www.patest.cn/contests/pat-a-practise/1023

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 struct bignum{

     int d[];

     int len;

     bignum(){

         memset(d,,sizeof(d));

         len=;

     }

 };

 int account[];// 统计origin中1~9各个数字出现次数

 char origin[];

 bignum str_to_bign(char str[]){

     bignum res;

     res.len=strlen(str);

     memset(account,,sizeof(account));

     for(int i=;i<res.len;i++){

         res.d[i]=str[res.len-i-]-'';

         account[res.d[i]]++;

     }

     return res;

 }

 bignum multi(bignum a,int b){

     bignum res;

     int carray=;

     for(int i=;i<a.len;i++){

         int temp=a.d[i]*b+carray;

         res.d[res.len++]=temp%;

         carray=temp/;

     }

     while(carray!=){

         res.d[res.len++]=carray%;

         carray/=;

     }

     return res;

 }

 bool isNumber(bignum a){

     if(a.len!=strlen(origin))

         return false;

     int num[]={};

     for(int i=;i<a.len;i++)

         num[a.d[i]]++;

     for(int i=;i<;i++)

         if(num[i]!=account[i])

             return false;

     return true;

 }

 void printbign(bignum a){

     for(int i=a.len-;i>=;i--)

         printf("%d",a.d[i]);

 }

 int main()

 {

     while(scanf("%s",origin)!=EOF){

         bignum a=str_to_bign(origin);

         a=multi(a,);

         if(isNumber(a))

             printf("Yes\n");

         else

             printf("No\n");

         printbign(a);

         printf("\n");

     }

     return ;

 }

A1024. Palindromic Number (25)

http://www.patest.cn/contests/pat-a-practise/1024

 #include <iostream>

 #include <cstring>

 using namespace std;

 struct bignum{

     int d[];

     int len;

     bignum(){

         memset(d,,sizeof(d));

         len=;

     }

 };

 bignum ChangeToBig(char str[]){

     bignum res;

     res.len=strlen(str);

     for(int i=;i<res.len;i++)

         res.d[i]=str[res.len--i]-'';

     return res;

 }

 bignum add(bignum a,bignum b){

     bignum res;

     int carray=;

     for(int i=;i<a.len || i<b.len;i++){

         int temp=a.d[i]+b.d[i]+carray;

         res.d[res.len++]=temp%;

         carray=temp/;

     }

     if(carray!=)

         res.d[res.len++]=carray;

     return res;

 }

 bignum reverseNum(bignum a){

     bignum res;

     res.len=a.len;

     for(int i=;i<res.len;i++)

         res.d[i]=a.d[res.len--i];

     return res;

 }

 bool isPalin(bignum a){

     int i=,j=a.len-;

     while(i<=j){

         if(a.d[i++]!=a.d[j--])

             return false;

     }

     return true;

 }

 void printBig(bignum a){

     for(int i=a.len-;i>=;i--)

         printf("%d",a.d[i]);

 }

 int main()

 {

     char str[];

     int k;

     while(scanf("%s%d",str,&k)!=EOF){

         bignum a=ChangeToBig(str);

         int step=;

         bignum b;

         while(step<k && !isPalin(a)){

             b=reverseNum(a);

             a=add(a,b);

             step++;

         }

         printBig(a);

         printf("\n%d\n",step);

     }

     return ;

 }