#include <stdio.h> #include <string.h> #include <stdlib.h>
const int OneNode = 1000000 ;//一位里不能超过OneNode const int NodeLen = 6 ;//一位储存NodeLen位,和OneNode必须同时更改,输出部分格式必须跟随这里!!! const int NumMax = 10005 ;//储存位数限制,真实位数为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"); } };
void Add(BigNum &a,BigNum &b,BigNum &c) // a+b ->c { unsigned lenmax = a.numlen>b.numlen?a.numlen:b.numlen; c.numlen = lenmax; unsigned i,carry=0; for ( i=0 ; i<lenmax ; i++ ) { c.num[i] = carry ; if( a.numlen > i ) c.num[i]+= a.num[i]; if( b.numlen > i ) c.num[i]+= b.num[i]; carry = c.num[i] / OneNode ; c.num[i] %= OneNode ; } if ( carry ) { c.num[i] = carry ; c.numlen ++; } }
void Mul(BigNum &a,BigNum &b,BigNum &c) // a*b ->c { unsigned carry = 0 , lenmax = a.numlen+b.numlen-1 ,i,j ; unsigned __int64 temp ; c.numlen = lenmax; for ( i=0 ; i<lenmax ; i++ ) { temp = carry ; for ( j=0 ; j<a.numlen ; j++ ) { if ( i<j ) break; if ( i-j >= b.numlen ) { j = i-b.numlen ; continue; } temp += (unsigned __int64)a.num[j] * b.num[i-j] ; } carry = temp / OneNode ; c.num[i] = temp % OneNode ; } if(carry) { c.num[i] = carry ; c.numlen ++; } while(c.numlen>1&&!c.num[c.numlen-1]) c.numlen--; }
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 Sub( BigNum &a , BigNum b ) //a-b -> a , a>=b { unsigned i = 0; unsigned carry = 0 ; for ( i=0 ; i<b.numlen ; i++ ) { a.num[i] = a.num[i]-carry-b.num[i]; if(a.num[i]>OneNode) //有进位(由于相减如果小于0会向上溢出) { a.num[i] += OneNode ; carry = 1; } else carry = 0; } while(carry) { if(a.num[i]) { a.num[i] --; carry = 0; } else { a.num[i] = OneNode-1; i++; } } while(a.num[a.numlen-1]==0 && a.numlen!=1) { a.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; }
一个很BT的大数运算。地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1001。 因为代码太长,所以分两部分打开,上面是大数一部分的代码
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
24 | 25 | 26 | 27 | 28 | 29 | 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 | 31 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|