设为首页收藏本站联系我们
切换到宽版

声振论坛

 找回密码
 我要加入

QQ登录

只需一步，快速开始

声振论坛»论坛 › 算法编程 › 算法及编程语言 › 标准整数(vector)
返回列表 发新帖
查看: 1671|回复: 0

[C/C++] 标准整数(vector)

[复制链接]
wugang_88
发表于 2006-11-22 10:45 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？我要加入

x
  1. #include<math.h>
  2. #include<iostream.h>
  3. #include<stdio.h>
  4. #include<conio.h>
  5. #include<vector>
  6. #define LL_MAX 100
  7. using namespace std;
  8. class LLong
  9. {
  10. private:
  11. vector<long> a;
  12. int m;
  13. int cp;
  14. private:
  15. int LL_BJ(const LLong &B);
  16. LLong Help_Add(const LLong &B);
  17. LLong Help_Sub(const LLong &B);
  18. void LL_Div01(const LLong &B,LLong &Q01,LLong &R01);
  19. void LL_Div02(const LLong &B,LLong &Q02,LLong &R02);
  20. void LL_Div03(const LLong &B,LLong &Q03,LLong &R03);
  21. void LL_Div(const LLong &B,LLong &Q,LLong &R);
  22. public:
  23. LLong();
  24. LLong(char *s);
  25. LLong(long d);
  26. ~LLong()
  27. { ;  }
  28. void print();
  29. long get_a(int n);
  30. int get_m();
  31. int get_cp();
  32. public:
  33. LLong operator+(const LLong &B);
  34. LLong operator-(const LLong &B);
  35. LLong operator*(const LLong &B);
  36. LLong operator^(const LLong &B);
  37. LLong operator%(const LLong &B);
  38. LLong operator/(const LLong &B);
  39. int operator==(const LLong &B);
  40. int operator!=(const LLong &B);
  41. int operator>(const LLong &B);
  42. int operator>=(const LLong &B){return(*this>B||*this==B);}
  43. int operator<(const LLong &B);
  44. int operator<=(const LLong &B){return(*this<B||*this==B);}
  45. };
  46. int main()
  47. {
  48. LLong a("8848");
  49. LLong b("4494");
  50. a.print();
  51. cout<<endl;
  52. b.print();
  53. cout<<endl;
  54. (a+b).print();
  55. cout<<endl;
  56. ((LLong)8-b).print();
  57. cout<<endl;
  58. (a*b).print();
  59. cout<<endl;
  60. (a*5).print();
  61. cout<<endl;
  62. (a/b).print();
  63. cout<<endl;
  64. (a%b).print();
  65. cout<<endl;
  66. (a^b).print();
  67. cout<<endl;
  68. a.print();
  69. cout<<endl;
  70. b.print();
  71. cout<<endl;
  72. if(a!=b)
  73.   cout<<"a!=b"<<endl;
  74. if(a>=b)
  75.   cout<<"a>=b"<<endl;
  76. if(a<=b)
  77.   cout<<"a<=b"<<endl;
  78. if(a<b)
  79.   cout<<"a<b"<<endl;
  80. else if(a==b)
  81.   cout<<"a==b"<<endl;
  82. else
  83.   cout<<"a>b"<<endl;
  84. return 0;
  85. }
  86. LLong::LLong()
  87. {
  88.   a.resize(LL_MAX);
  89.   a[0]=0;
  90.   m=0;
  91.   cp=0;
  92. }
  93. LLong::LLong(char *s)
  94. {
  95. int n,i,t;
  96. a.resize(LL_MAX);
  97. if(*s=='-')
  98. {
  99.   cp=1;
  100.   n=-1;
  101. }
  102. else if(*s=='+')
  103. {
  104.   cp=0;
  105.   n=-1;
  106. }
  107. else
  108. {
  109.   cp=0;
  110.   n=0;
  111. }
  112. while(*s!='\0')
  113. {
  114.   n++;
  115.   s++;
  116. }
  117. if(n%4==0)
  118. {
  119.   n=n/4;
  120.   t=4;
  121. }
  122. else
  123. {
  124.   t=n%4;
  125.   n=n/4+1;
  126. }
  127. if(n==0)
  128.   cout<<"Not have dat"<<endl;
  129. if(n>LL_MAX)
  130.   a.resize(n);
  131. m=n-1;
  132. for(i=0;i<n-1;i++)
  133.   a[i]=*(s-1-4*i)-48+(*(s-2-4*i)-48)*10+
  134.    (*(s-3-4*i)-48)*100+(*(s-4-4*i)-48)*1000;
  135. a[n-1]=0;
  136. for(i=1;i<=t;i++)
  137.   a[n-1]=a[n-1]+(*(s-i-4*(n-1))-48)*(int)pow(10,i-1);
  138. }
  139. LLong::LLong(long d)
  140. {
  141. a.resize(LL_MAX);
  142. if(d<0)
  143.   cp=1;
  144. else
  145.   cp=0;
  146. d=abs(d);
  147. if(d<10000)
  148. {
  149.   m=0;
  150.   a[0]=d;
  151. }
  152. else if(d<100000000)
  153. {
  154.   m=1;
  155.   a[0]=d%10000;
  156.   d=(d-d%10000)/10000;
  157.   a[1]=d%10000;
  158. }
  159. else
  160. {
  161.   m=2;
  162.   a[0]=d%10000;
  163.   d=(d-d%10000)/10000;
  164.   a[1]=d%10000;
  165.   d=(d-d%10000)/10000;
  166.   a[2]=d%10000;
  167. }
  168. }
  169. void LLong::print()
  170. {
  171. long i,b[4];
  172. char aa[4];
  173. if(cp==1)
  174.   printf("-");
  175. printf("%ld",a[m]);
  176. for(i=m-1;i>=0;i--)
  177. {
  178.   b[0]=a[i]%10;
  179.   b[1]=((a[i]-b[0])/10)%10;
  180.   b[2]=((a[i]-b[0]-b[1]*10)/100)%10;
  181.   b[3]=((a[i]-b[0]-b[1]*10-b[2]*100)/1000)%10;
  182.   aa[0]=b[0]+48;
  183.   aa[1]=b[1]+48;
  184.   aa[2]=b[2]+48;
  185.   aa[3]=b[3]+48;
  186.   printf("%c%c%c%c",aa[3],aa[2],aa[1],aa[0]);
  187. }

  189. }
  190. long LLong::get_a(int n)
  191. {
  192. if((n>m)||(n<0))
  193. {
  194.   cout<<"溢出"<<endl;
  195.   return 0;
  196. }
  197. else
  198.   return a[n];
  199. }
  200. int LLong::get_cp()
  201. {
  202. return cp;
  203. }
  204. int LLong::get_m()
  205. {
  206. return m;
  207. }
  208. int LLong::LL_BJ(const LLong &B)
  209. {
  210. int i;
  211. if(m>B.m)
  212.   return 1;
  213. else if(m<B.m)
  214.   return -1;
  215. else
  216. {
  217.   for(i=m;i>=0;i--)
  218.   {
  219.    if(a[i]>B.a[i])
  220.     return 1;
  221.    else if(a[i]<B.a[i])
  222.     return -1;
  223.   }
  224.   return 0;
  225. }
  226. }
  227. int LLong::operator==(const LLong &B)
  228. {
  229. if(cp!=B.cp)
  230.   return 0;
  231. if(LL_BJ(B)==0)
  232.   return 1;
  233. else
  234.   return 0;
  235. }
  236. int LLong::operator!=(const LLong &B)
  237. {
  238. if((LL_BJ(B)==0)&&(cp==B.cp))
  239.   return 0;
  240. else
  241.   return 1;
  242. }
  243. int LLong::operator<(const LLong &B)
  244. {
  245. if(cp>B.cp)
  246.   return 1;
  247. else if(cp<B.cp)
  248.   return 0;
  249. else
  250. {
  251.   if(((cp==0)&&(LL_BJ(B)==-1))||((cp==1)&&(LL_BJ(B)==1)))
  252.    return 1;
  253.   else
  254.    return 0;
  255. }
  256.   
  257. }
  258. int LLong::operator>(const LLong &B)
  259. {
  260. if(cp>B.cp)
  261.   return 0;
  262. else if(cp<B.cp)
  263.   return 1;
  264. else
  265. {
  266.   if(((cp==0)&&(LL_BJ(B)==1))||((cp==1)&&(LL_BJ(B)==-1)))
  267.    return 1;
  268.   else
  269.    return 0;
  270. }
  271. }
  272. LLong LLong::Help_Add(const LLong &B)
  273. {
  274. LLong D;
  275. int i;
  276. for(i=0;i<=m;i++)
  277. {
  278.   if(i<=B.m)
  279.   {
  280.    if(i+2>LL_MAX)D.a.resize(i+2);
  281.    D.a[i+1]=(D.a[i]+a[i]+B.a[i])/10000;
  282.    D.a[i]=(D.a[i]+a[i]+B.a[i])%10000;
  283.   }
  284.   else
  285.   {
  286.    if(i+2>LL_MAX)D.a.resize(i+2);
  287.    D.a[i+1]=(D.a[i]+a[i])/10000;
  288.    D.a[i]=(D.a[i]+a[i])%10000;
  289.   }
  290. }
  291. if(D.a[m+1]==0)
  292.   D.m=m;
  293. else
  294.   D.m=m+1;
  295. return D;
  296. }
  297. LLong LLong::Help_Sub(const LLong &B)
  298. {
  299. LLong D;
  300. int i,y=0;
  301. for(i=0;i<=m;i++)
  302. {
  303.   if(i<=B.m)
  304.   {
  305.    if(a[i]-y>=B.a[i])
  306.    {   
  307. if(i+1>LL_MAX)D.a.resize(i+1);
  308.     D.a[i]=a[i]-y-B.a[i];
  309.     y=0;
  310.    }
  311.    else
  312.    {   
  313. if(i+1>LL_MAX)D.a.resize(i+1);
  314.     D.a[i]=10000+a[i]-y-B.a[i];
  315.     y=1;
  316.    }
  317.   }
  318.   else
  319.   {
  320.    if(a[i]-y>=0)
  321.    {
  322. if(i+1>LL_MAX)D.a.resize(i+1);
  323.     D.a[i]=a[i]-y;
  324.     y=0;
  325.    }
  326.    else
  327.    {
  328. if(i+1>LL_MAX)D.a.resize(i+1);
  329.     D.a[i]=10000+a[i]-y;
  330.     y=1;
  331.    }
  332.   }
  333. }
  334. for(i=m;i>=0;i--)
  335.   if(D.a[i]!=0)
  336.   {
  337.    D.m=i;
  338.    break;
  339.   }
  340. return D;
  341. }
  342. LLong LLong::operator+(const LLong &B)
  343. {
  344. LLong D,AA,BB=B;
  345. if(m+1>LL_MAX)AA.a.resize(m+1);
  346. for(int i=0;i<=m;i++)
  347.   AA.a[i]=a[i];
  348. AA.m=m;
  349. AA.cp=cp;
  350. if((LL_BJ(BB)==1)||(LL_BJ(BB)==0))
  351. {
  352.   if(cp==B.cp)
  353.   {
  354.    D=Help_Add(BB);
  355.    D.cp=cp;
  356.   }
  357.   else if((cp==0)&&(B.cp==1))
  358.   {
  359.    D=Help_Sub(BB);
  360.    D.cp=0;
  361.   }
  362.   else
  363.   {
  364.    D=Help_Sub(BB);
  365.    D.cp=1;
  366.   }
  367. }
  368. else
  369. {
  370.   if(BB.m+1>LL_MAX)
  371. a.resize(BB.m+1);
  372.   cp=BB.cp;m=BB.m;
  373.   for(i=0;i<=BB.m;i++)
  374.    a[i]=BB.a[i];
  375.   BB=AA;
  376.   if(cp==BB.cp)
  377.   {
  378.    D=Help_Add(BB);
  379.    D.cp=cp;
  380.   }
  381.   else if((cp==0)&&(BB.cp==1))
  382.   {
  383.    D=Help_Sub(BB);
  384.    D.cp=0;
  385.   }
  386.   else
  387.   {
  388.    D=Help_Sub(BB);
  389.    D.cp=1;
  390.   }
  391. }
  392. if(AA.m+1>LL_MAX)a.resize(AA.m+1);
  393. cp=AA.cp;
  394. m=AA.m;
  395. for(i=0;i<=AA.m;i++)
  396.   a[i]=AA.a[i];
  397. return D;
  398. }
  399. LLong LLong::operator-(const LLong &B)
  400. {
  401. LLong D,AA,BB=B;
  402. if(m+1>LL_MAX)AA.a.resize(m+1);
  403. for(int i=0;i<=m;i++)
  404.   AA.a[i]=a[i];
  405. AA.m=m;
  406. AA.cp=cp;
  407. if((LL_BJ(BB)==1)||(LL_BJ(BB)==0))
  408. {
  409.   if(cp==BB.cp)
  410.   {
  411.    D=Help_Sub(BB);
  412.    D.cp=cp;
  413.   }
  414.   else if((cp==0)&&(BB.cp==1))
  415.   {
  416.    D=Help_Add(BB);
  417.    D.cp=0;
  418.   }
  419.   else
  420.   {
  421.    D=Help_Add(BB);
  422.    D.cp=1;
  423.   }
  424. }
  425. else
  426. {
  427.   if(BB.m+1>LL_MAX)
  428. a.resize(BB.m+1);
  429.   cp=BB.cp;m=BB.m;
  430.   for(i=0;i<=BB.m;i++)
  431.    a[i]=BB.a[i];
  432.   BB=AA;
  433.   if(cp==BB.cp)
  434.   {
  435.    D=Help_Sub(BB);
  436.    if(cp==1)
  437.     D.cp=0;
  438.    if(cp==0)
  439.     D.cp=1;
  440.   }
  441.   else if((cp==0)&&(BB.cp==1))
  442.   {
  443.    D=Help_Add(BB);
  444.    D.cp=1;
  445.   }
  446.   else
  447.   {
  448.    D=Help_Add(BB);
  449.    D.cp=0;
  450.   }
  451. }
  452. if(AA.m+1>LL_MAX)a.resize(AA.m+1);
  453. cp=AA.cp;
  454. m=AA.m;
  455. for(i=0;i<=m;i++)
  456.   a[i]=AA.a[i];
  457. return D;
  458. }
  459. LLong LLong::operator*(const LLong &B)
  460. {
  461. LLong F,D;
  462. int i,j,k;
  463. if(cp==B.cp)
  464.   k=0;
  465. else
  466.   k=1;
  467. LLong G=B;
  468. G.cp=0;
  469. for(j=0;j<=G.m;j++)
  470. {
  471.   for(i=0;i<j+m+2;i++)/*sugaigua*/
  472.   {
  473.    if(i+1>LL_MAX)
  474.     D.a.resize(i+1);  
  475.    D.a[i]=0;
  476.   }
  477.   D.m=j+m+1;
  478.   for(i=j;i<=j+m;i++)
  479.   {
  480.    D.a[i+1]=(D.a[i]+G.a[j]*a[i-j])/10000;
  481.    D.a[i]=(D.a[i]+G.a[j]*a[i-j])%10000;
  482.   }
  483.   if(D.a[j+m+1]==0)
  484.    D.m=j+m;
  485.   D.cp=0;
  486.   F=F+D;
  487. }
  488. F.cp=k;
  489. return F;
  490. }
  491. LLong LLong::operator^(const LLong &B)
  492. {
  493. LLong AA,d,W,BB=B,T(1),D(1);
  494. if(BB<W)
  495. {
  496.   cout<<"指数不能负"<<endl;
  497.   return 1;
  498. }
  499. if(m+1>LL_MAX)AA.a.resize(m+1);
  500. AA.m=m;
  501. AA.cp=cp;
  502. for(int i=0;i<=m;i++)
  503.   AA.a[i]=a[i];
  504. for(d=W;d<BB;d=d+T)
  505. {
  506.   D=D*AA;
  507. }
  508. return D;
  509. }
  510. void LLong::LL_Div01(const LLong &B,LLong &Q,LLong &R)
  511. {
  512. int i,n;
  513. LLong F,W,T(1);
  514. LLong AA,BB=B;
  515. if(m+1>LL_MAX)AA.a.resize(m+1);
  516. AA.m=m;
  517. AA.cp=cp;
  518. for(i=0;i<=m;i++)
  519.   AA.a[i]=a[i];
  520. AA.cp=BB.cp=0;
  521. if(LL_BJ(BB)==-1)
  522. {
  523.   R=AA;
  524.   Q=W;
  525. }
  526. else if(LL_BJ(BB)==0)
  527. {
  528.   R=W;
  529.   Q=T;
  530. }
  531. else
  532. {
  533.   n=AA.m-BB.m;
  534.   for(i=0;i<n;i++)
  535.   {
  536.    if(i+1>LL_MAX)
  537.     F.a.resize(i+1);
  538.    F.a[i]=0;
  539.   }
  540.   if(AA.a[AA.m]>=BB.a[BB.m])
  541.   {
  542.    if(n+1>LL_MAX)F.a.resize(n+1);
  543.    F.a[n]=AA.a[AA.m]/BB.a[BB.m];
  544.    F.m=n;
  545.   }
  546.   else
  547.   {
  548.    F.a[n-1]=(AA.a[AA.m]*10000+AA.a[AA.m-1])/BB.a[BB.m];
  549.    F.m=n-1;
  550.   }
  551.   F.cp=0;
  552.   Q=F;
  553.   R=AA-BB*F;
  554. }
  555. }
  556. void LLong::LL_Div02(const LLong &B,LLong &Q,LLong &R)
  557. {
  558. LLong W,AA,BB=B;
  559. if(m+1>LL_MAX)AA.a.resize(m+1);
  560. AA.m=m;
  561. AA.cp=cp;
  562. for(int i=0;i<=m;i++)
  563.   AA.a[i]=a[i];
  564. BB.cp=0;
  565. if(cp==0)
  566.   LL_Div01(BB,Q,R);
  567. else
  568. {
  569.   LL_Div01(BB,Q,R);
  570. if(Q!=W)
  571.    Q.cp=1;
  572. if(R!=W)
  573.   {
  574.    if(R.cp==0)
  575.     R.cp=1;
  576.    else
  577.     R.cp=0;
  578.   }
  579. }
  580.    if(AA.m+1>LL_MAX)a.resize(AA.m+1);
  581.    cp=AA.cp;
  582.    m=AA.m;
  583.    for(i=0;i<=AA.m;i++)
  584.     a[i]=AA.a[i];
  585.    return;
  586. }
  587. void LLong::LL_Div03(const LLong &B,LLong &Q,LLong &R)
  588. {
  589. LLong W,AAA,AA,QQ,RR,T(1),BB=B;
  590. if(m+1>LL_MAX)AA.a.resize(m+1);
  591. AA.m=m;
  592. AA.cp=cp;
  593. for(int i=0;i<=m;i++)
  594.   AA.a[i]=a[i];
  595. AAA=AA;
  596. AA.cp=BB.cp=0;
  597. while(1)
  598. {
  599.   LL_Div02(BB,QQ,RR);
  600.   if(RR.m+1>LL_MAX)a.resize(RR.m+1);
  601.   cp=RR.cp;
  602.   m=RR.m;
  603.   for(i=0;i<=RR.m;i++)
  604.    a[i]=RR.a[i];
  605.   if(LL_BJ(BB)==-1)
  606.   {
  607.    if(RR.cp==0)
  608.    {
  609.     R=RR;
  610.     Q=Q+QQ;
  611.    }
  612.    else
  613.    {
  614.     R=BB+RR;
  615.     Q=Q+QQ-T;
  616.    }
  617.    if(AAA.m+1>LL_MAX)a.resize(AAA.m+1);
  618.    cp=AAA.cp;
  619.    m=AAA.m;
  620.    for(i=0;i<=AAA.m;i++)
  621.     a[i]=AAA.a[i];
  622.    return;
  623.   }
  624.    if(RR.m+1>LL_MAX)a.resize(RR.m+1);
  625.    cp=RR.cp;
  626.    m=RR.m;
  627.    for(i=0;i<=RR.m;i++)
  628.     a[i]=RR.a[i];
  629.    Q=Q+QQ;
  630.   
  631. }
  632. }
  633. void LLong::LL_Div(const LLong &B,LLong &Q,LLong &R)
  634. {
  635. LLong W,AA,BB=B,AAA;
  636. if(m+1>LL_MAX)AA.a.resize(m+1);
  637. AA.m=m;
  638. AA.cp=cp;
  639. for(int i=0;i<=m;i++)
  640.   AA.a[i]=a[i];
  641. AAA=AA;
  642. if(BB==W)
  643. printf("Not to Div.");
  644. if((AA.cp==0)&&(BB.cp==0))
  645.   LL_Div03(BB,Q,R);
  646. else if((AA.cp==1)&&(BB.cp==1))
  647. {
  648.   cp=0;BB.cp=0;
  649.   LL_Div03(BB,Q,R);
  650. }
  651. else if((AA.cp==1)&&(BB.cp==0))
  652. {
  653.   cp=0;
  654.   LL_Div03(BB,Q,R);
  655. if(Q!=W)
  656.   Q.cp=1;
  657. if(R!=W)
  658.    R.cp=1;
  659. }
  660. else
  661. {
  662.   LL_Div03(BB,Q,R);
  663. if(Q!=W)
  664.    Q.cp=1;
  665. }
  666.    if(AAA.m+1>LL_MAX)a.resize(AAA.m+1);
  667.    cp=AAA.cp;
  668.    m=AAA.m;
  669.    for(i=0;i<=AAA.m;i++)
  670.     a[i]=AAA.a[i];
  671.    return;
  672. }
  673. LLong LLong::operator%(const LLong &B)
  674. {
  675. LLong Q,R;
  676. LL_Div(B,Q,R);
  677. return R;
  678. }

  680. LLong LLong::operator/(const LLong &B)
  681. {
  682. LLong Q,R;
  683. LL_Div(B,Q,R);
  684. return Q;
  685. }
复制代码

[ 本帖最后由 风花雪月 于 2006-11-29 07:30 编辑 ]

评分

1

查看全部评分

回复
分享到：

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-5-11 13:50 , Processed in 0.063640 second(s), 19 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表