[关闭]
@Junlier 2018-09-24T23:00:14.000000Z 字数 2897 阅读 2128

高精度模板汇总

算法——高精度

高精加高精

很简单,直接做就行了

  1. string S;
  2. struct GJ{
  3. int s[N],L;
  4. void Print()
  5. {
  6. for(int i=L;i>1;--i)
  7. printf("%d",s[i]);
  8. printf("%d\n",s[1]);
  9. }
  10. }blank,A,B,Ans;
  11. GJ operator +(GJ X,GJ Y)
  12. {
  13. GJ mid=blank;
  14. mid.L=max(X.L,Y.L);
  15. for(int i=1;i<=mid.L;++i)
  16. {
  17. mid.s[i]+=X.s[i]+Y.s[i];
  18. mid.s[i+1]+=mid.s[i]/10;
  19. mid.s[i]%=10;
  20. }
  21. if(mid.s[mid.L+1])mid.L++;
  22. return mid;
  23. }
  24. int main()
  25. {
  26. cin>>S;A.L=S.length();
  27. for(int i=0;i<A.L;++i)
  28. A.s[A.L-i]=S[i]-'0';
  29. cin>>S;B.L=S.length();
  30. for(int i=0;i<B.L;++i)
  31. B.s[B.L-i]=S[i]-'0';
  32. Ans=A+B;
  33. Ans.Print();
  34. return 0;
  35. }

高精减高精

注意一下判断高精的大小关系
我偷懒就直接用string的库函数了。。。

  1. string S1,S2;
  2. struct GJ{
  3. int s[N],L;
  4. void Print()
  5. {
  6. for(int i=L;i>1;--i)
  7. printf("%d",s[i]);
  8. printf("%d\n",s[1]);
  9. }
  10. }blank,A,B,Ans;
  11. GJ operator -(GJ X,GJ Y)
  12. {
  13. GJ mid=blank;
  14. mid.L=max(X.L,Y.L);
  15. for(int i=1;i<=mid.L;++i)
  16. {
  17. mid.s[i]+=X.s[i]-Y.s[i];
  18. if(mid.s[i]<0)
  19. mid.s[i+1]--,mid.s[i]+=10;
  20. }
  21. while(!mid.s[mid.L]&&mid.L>1)mid.L--;
  22. return mid;
  23. }
  24. int main()
  25. {
  26. bool flag=0;
  27. cin>>S1;A.L=S1.length();
  28. cin>>S2;B.L=S2.length();
  29. if(A.L<B.L||(A.L==B.L&&S1<S2))
  30. {
  31. swap(S1,S2);
  32. swap(A.L,B.L),flag=1;
  33. }
  34. for(int i=0;i<A.L;++i)
  35. A.s[A.L-i]=S1[i]-'0';
  36. for(int i=0;i<B.L;++i)
  37. B.s[B.L-i]=S2[i]-'0';
  38. Ans=A-B;
  39. if(flag)putchar('-');
  40. Ans.Print();
  41. return 0;
  42. }

高精乘高精

小数的话先把小数点抠出来,在答案里加进去就ok
负数的话特判一下就可以了

  1. char S[N];
  2. struct GJ{
  3. int s[N],L;
  4. void Print()
  5. {
  6. for(int i=L;i>1;--i)
  7. printf("%d",s[i]);
  8. printf("%d\n",s[1]);
  9. }
  10. }blank,A,B,Ans;
  11. GJ operator *(GJ X,GJ Y)
  12. {
  13. GJ mid=blank;
  14. mid.L=X.L+Y.L;
  15. for(int i=1;i<=X.L;++i)
  16. for(int j=1;j<=Y.L;++j)
  17. {
  18. mid.s[i+j-1]+=X.s[i]*Y.s[j];
  19. mid.s[i+j]+=mid.s[i+j-1]/10;
  20. mid.s[i+j-1]%=10;
  21. }
  22. while(!mid.s[mid.L]&&mid.L>1)mid.L--;
  23. return mid;
  24. }
  25. int main()
  26. {
  27. cin>>S;A.L=strlen(S);
  28. for(int i=0;i<A.L;++i)
  29. A.s[A.L-i]=S[i]-'0';
  30. cin>>S;B.L=strlen(S);
  31. for(int i=0;i<B.L;++i)
  32. B.s[B.L-i]=S[i]-'0';
  33. Ans=A*B;
  34. Ans.Print();
  35. return 0;
  36. }

高精除低精

被除数 ,除数,答案 。。。

  1. lst now=0;
  2. for(int i=1;i<=len;++i)
  3. {
  4. now=now*10+a[i];
  5. ans[++cnt]=now/B;
  6. now=now%B;
  7. }bool flag=0;
  8. for(int i=1;i<=cnt;++i)
  9. {
  10. if(ans[i])flag=1;
  11. if(flag)printf("%d",ans[i]);
  12. }puts("");

高精除高精

不停地做高精减就可以了。。。
这个代码是的,别介意。。。

  1. int compare(int aa[],int bb[])
  2. {
  3. if(aa[0]>bb[0])return 1;
  4. if(aa[0]<bb[0])return -1;
  5. for(int i=aa[0];i>0;i--)
  6. {
  7. if(aa[i]>bb[i])return 1;
  8. if(aa[i]<bb[i])return -1;
  9. }
  10. return 0;
  11. }
  12. void numcpy(int aa[],int bb[],int l)
  13. {
  14. for(int i=1;i<=aa[0];i++)bb[i+l-1]=aa[i];
  15. bb[0]=aa[0]+l-1;
  16. }
  17. int main()
  18. {
  19. cin>>a1>>b1;a[0]=a1.size();
  20. b[0]=b1.size(),c[0]=a[0]-b[0]+1;
  21. for(int i=1;i<=a[0];i++)a[i]=a1[a[0]-i]-'0';
  22. for(int i=1;i<=b[0];i++)b[i]=b1[b[0]-i]-'0';
  23. for(int i=c[0];i>0;i--)
  24. {
  25. memset(t,0,sizeof(t));
  26. numcpy(b,t,i);
  27. while(compare(a,t)>=0)
  28. {
  29. c[i]++;
  30. if(!compare(a,t)){a[0]=0;continue;}
  31. for(int i=1;i<=a[0];i++)
  32. {
  33. if(a[i]<t[i])
  34. a[i+1]--,a[i]+=10;
  35. a[i]-=t[i];
  36. }
  37. while(a[0]>0&&!a[a[0]])a[0]--;
  38. }
  39. }
  40. while(c[0]>0&&!c[c[0]])c[0]--;
  41. if(!c[0])puts("0");
  42. else for(int i=c[0];i>0;i--)cout<<c[i];
  43. return 0;
  44. }

高精取模低精

你把读入优化的板子改一下,一边读一边就行了。。。

  1. int Read(lst n)
  2. {
  3. lst x=0;char ch=getchar();
  4. while(!(ch>='0'&&ch<='9'))ch=getchar();//还不要判负数。。。
  5. while( (ch>='0'&&ch<='9'))x=(x*10+ch-'0')%n,ch=getchar();
  6. return x?x:n;
  7. }
  8. int main()
  9. {
  10. scanf("%lld",&n);
  11. cout<<Read(n)<<endl;
  12. }

尾言

其实这些都可以放进一个程序operator
我就懒得再弄了
高精还是很简单的,就是写得烦
如今很多题目都采用取模的方法避免高精,所以掌握就行了
我也就是Noip前练习一下而已。。。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注