大数的运算,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=2325
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int OneNode = 1000000; //??????????????OneNode
const int NodeLen = 6; //????????NodeLen??????OneNode????????????,????????????????????????!!!
const int NumMax = 1005; //????????????????????????NumMax*6
struct BigNum
  {
unsigned num[NumMax] ;//???? ?? ????????
unsigned numlen ;
 void set(unsigned sm=0) { num[0] = sm ; numlen = 1; }//sm<OneNode
void set(char *string , int strlen)
 {
numlen = (strlen-1) / NodeLen + 1 ;
memset (num , 0 , sizeof(unsigned)*numlen );
int temp , i ;
for( i=strlen-1 ; i>=0 ; i-- )
 {
temp = i / NodeLen ;
num[temp] = num[temp]*10 + string[strlen-1-i]-'0' ;
}
}
void print()
 {
printf("%d",num[numlen-1]);
int i = numlen-1;
while( i )
 {
i--;
printf("%06d",num[i]);
}
printf("\n");
}
};

int Cmp(BigNum &a,BigNum &b) //a>b --> 1 , > --> -1 ,== --> 0
  {
if( a.numlen>b.numlen )
return 1;
if( a.numlen<b.numlen )
return -1;
int len = a.numlen ;
while(len)
 {
len --;
if(a.num[len]>b.num[len])return 1;
if(a.num[len]<b.num[len])return -1;
}
return 0;
}

void Cpy(BigNum &a , BigNum &b) //b-->a
  {
a.numlen=b.numlen;
memcpy(a.num,b.num,sizeof(unsigned)*b.numlen);
}

void Div(BigNum &a,int b,int &l) // a/=b -> ????l
  {
int carry=0;
int i;
for(i=a.numlen-1;i>=0;i--)
 {
a.num[i]+=carry*OneNode;
carry=a.num[i]%b;
a.num[i]/=b;
}
if(a.numlen>1&&!a.num[a.numlen-1])a.numlen--;
l=carry;
}

 int dig[9] = {1,2,3,4,5,6,7,8,9};

BigNum a, b, c;

char input[1005];

int ans[1005];

int main()
  {

int i;
int p;
int l;
int flag;
while (1)
 {
scanf("%s", &input);
if (input[0]=='-')
 {
break;
}
a.set(input, strlen(input));
c.set("10", 2);
if (Cmp(a, c)<0)
 {
printf("1");
a.print();
}
else
 {
p = -1;
flag = 0;
while (Cmp(a, c)>=0)
 {
for (i=8; i>0; i--)
 {
Cpy(b, a);
Div(b, dig[i], l);
if (l==0)
 {
flag = 1;
ans[++p] = dig[i];
Cpy(a, b);
break;
}
}
if (!flag)
 {
p = -1;
break;
}
else
 {
flag = 0;
}
}
if (Cmp(a, c)<0)
 {
for (i=8; i>=0; i--)
 {
Cpy(b, a);
Div(b, dig[i], l);
if (l==0)
 {
ans[++p] = dig[i];
break;
}
}
}
if (p!=-1)
 {
for (i=p; i>=0; i--)
 {
printf("%d", ans[i]);
}
printf("\n");
}
else
 {
printf("There is no such number.\n");
}
}
}
return 0;
}


|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|