当前位置：首页 > news >正文

PAT 大数运算

news 来源：原创 2024/4/29 6:27:31

2019独角兽企业重金招聘Python工程师标准>>>

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

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N=1010;
 5 struct bignum{
 6     int d[N];
 7     int len;
 8     bignum(){
 9         memset(d,0,sizeof(d));
10         len=0;
11     }
12 };
13 bignum change(char str[]){
14     bignum res;
15     res.len=strlen(str);
16     for(int i=0;i<res.len;i++)
17         res.d[i]=str[res.len-1-i]-'0';
18     return res;
19 }
20 bignum divide(bignum a,int b,int &r){
21     bignum res;
22     res.len=a.len;
23     for(int i=res.len-1;i>=0;i--){
24         r=r*10+a.d[i];
25         if(r<b)
26             res.d[i]=0;
27         else{
28             res.d[i]=r/b;
29             r%=b;
30         }
31     }
32     while(res.len>1 && res.d[res.len-1]==0)
33         res.len--;
34     return res;
35 }
36 void printbign(bignum t){
37     for(int i=t.len-1;i>=0;i--)
38         printf("%d",t.d[i]);
39 }
40 int main()
41 {
42     char A[N];
43     int B;
44     while(scanf("%s%d",A,&B)!=EOF){
45         bignum a,q;
46         int r=0;
47         a=change(A);
48         q=divide(a,B,r);
49         printbign(q);
50         printf(" %d\n",r);        
51     }
52     return 0;
53 }

View Code

A1023. Have Fun with Numbers (20)

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

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 struct bignum{
 6     int d[21];
 7     int len;
 8     bignum(){
 9         memset(d,0,sizeof(d));
10         len=0;
11     }
12 };
13 int account[10];// 统计origin中1~9各个数字出现次数 
14 char origin[21];
15 bignum str_to_bign(char str[]){
16     bignum res;
17     res.len=strlen(str);
18     memset(account,0,sizeof(account));
19     for(int i=0;i<res.len;i++){
20         res.d[i]=str[res.len-i-1]-'0';
21         account[res.d[i]]++;        
22     }
23     return res;
24 }
25 bignum multi(bignum a,int b){
26     bignum res;
27     int carray=0;
28     for(int i=0;i<a.len;i++){
29         int temp=a.d[i]*b+carray;
30         res.d[res.len++]=temp%10;
31         carray=temp/10;
32     }
33     while(carray!=0){
34         res.d[res.len++]=carray%10;
35         carray/=10;
36     }
37     return res;
38 }
39 bool isNumber(bignum a){
40     if(a.len!=strlen(origin))
41         return false;
42     int num[10]={0};
43     for(int i=0;i<a.len;i++)
44         num[a.d[i]]++;
45     for(int i=0;i<10;i++)
46         if(num[i]!=account[i])
47             return false;
48     return true;
49 }
50 void printbign(bignum a){
51     for(int i=a.len-1;i>=0;i--)
52         printf("%d",a.d[i]);
53 }
54 int main()
55 {
56     while(scanf("%s",origin)!=EOF){
57         bignum a=str_to_bign(origin);
58         a=multi(a,2);
59         if(isNumber(a))
60             printf("Yes\n");
61         else
62             printf("No\n");
63         printbign(a);
64         printf("\n");
65     }
66     return 0;
67 }

View Code

A1024. Palindromic Number (25)

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

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 struct bignum{
 5     int d[1000];
 6     int len;
 7     bignum(){
 8         memset(d,0,sizeof(d));
 9         len=0;
10     }
11 };
12 bignum ChangeToBig(char str[]){
13     bignum res;
14     res.len=strlen(str);
15     for(int i=0;i<res.len;i++)
16         res.d[i]=str[res.len-1-i]-'0';
17     return res;
18 }
19 bignum add(bignum a,bignum b){
20     bignum res;
21     int carray=0;
22     for(int i=0;i<a.len || i<b.len;i++){
23         int temp=a.d[i]+b.d[i]+carray;
24         res.d[res.len++]=temp%10;
25         carray=temp/10;
26     }
27     if(carray!=0)
28         res.d[res.len++]=carray;
29     return res;
30 }
31 bignum reverseNum(bignum a){
32     bignum res;
33     res.len=a.len;
34     for(int i=0;i<res.len;i++)
35         res.d[i]=a.d[res.len-1-i];
36     return res;
37 }
38 bool isPalin(bignum a){
39     int i=0,j=a.len-1;
40     while(i<=j){
41         if(a.d[i++]!=a.d[j--])
42             return false;
43     }
44     return true;
45 }
46 void printBig(bignum a){
47     for(int i=a.len-1;i>=0;i--)
48         printf("%d",a.d[i]);
49 }
50 int main()
51 {
52     char str[1000];
53     int k;
54     while(scanf("%s%d",str,&k)!=EOF){
55         bignum a=ChangeToBig(str);
56         int step=0;
57         bignum b;
58         while(step<k && !isPalin(a)){
59             b=reverseNum(a);
60             a=add(a,b);
61             step++;
62         }
63         printBig(a);
64         printf("\n%d\n",step);
65     }
66     return 0;
67 }

View Code