PAT 大数运算

时间:2021-09-27 09:22:42

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 ;
}