大數開方模版：

題目：大數開方

?

#include <stdio.h> #include <string.h> #include <stdlib.h>#define DEPTH 10typedef int BigInteger[10100];int comp(const BigInteger a,const int c,const int d,const BigInteger b) //大數比較 {int i,t=0,O=-DEPTH*2;if(b[0]-a[0]<d&&c) return 1;for(i=b[0];i>d;i--){t=t*DEPTH+a[i-d]*c-b[i];if(t>0) return 1;if(t<O) return 0;}for(i=d;i;i--){t=t*DEPTH-b[i];if(t>0) return 1;if(t<O) return 0;}return t>0; }void sub(BigInteger a,const BigInteger b,const int c,const int d) //大數減 {int i,O=b[0]+d;for(i=1+d;i<=O;i++)if((a[i]-=b[i-d]*c)<0)a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH;for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);for(;!a[a[0]]&&a[0]>1;a[0]--); }void Sqrt(BigInteger b,BigInteger a) //開平方 {int h,l,m,i;memset((void*)b,0,sizeof(BigInteger));for(i= b[0]=(a[0]+1)>>1;i;sub(a,b,m,i-1),b[i]+=m,i--)for(h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)if(comp(b,m,i-1,a)) h=m-1;else l = m;for(;!b[b[0]]&&b[0]>1;b[0]--);for (i = 1; i <= b[0]; b[i++] >>= 1); }char str[10100]; BigInteger a,b;int main() {int t;scanf("%d", &t);while(t--){scanf("%s",str);a[0]=strlen(str);for(int i=1; i<=a[0]; i++)a[i]=str[a[0]-i]-'0';Sqrt(b,a);for(int i=b[0]; i>=1; i--)printf("%d",b[i]);printf("\n");if(t)puts("");}return 0; }

?

題目：1153. Supercomputer

題目大意：N=x*(x+1)/2，給你N (N < 10⁶⁰⁰)，輸出x

分析：求sqrt(2*N)即可

#include <iostream> #include <string.h> #include <cstdlib> #include <stdio.h> #include <algorithm> using namespace std;#define MAXN 20000int big(char s1[],char s2[]) {int len1,len2,i,q;q=0;while(s1[q]=='0') q++;strcpy(s1,s1+q);if(strlen(s1)==0){s1[0]='0';s1[1]=0;}q=0;while(s2[q]=='0') q++;strcpy(s2,s2+q);if(strlen(s2)==0){s2[0]='0';s2[1]=0;}len1=strlen(s1);len2=strlen(s2);if(len1>len2)return 1;else if(len1<len2)return 0;else{for(i=0;i<len1;i++){if(s1[i]>s2[i])return 1;else if(s1[i]<s2[i])return 0;}}return 0; }void mul(char s[],int t,char re[]) //乘 {int left,i,j,k,len;char c;left=0;j=0;for(i=strlen(s)-1;i>=0;i--){k=t*(s[i]-'0')+left;re[j++]=(k%10)+'0';left=k/10;}while(left>0){re[j++]=(left%10)+'0';left/=10;}re[j]=0;len=strlen(re);for(i=0;i<len/2;i++){c=re[i];re[i]=re[len-1-i];re[len-1-i]=c;}return; }void sub(char a[],char b[]) //減 {int left,len1,len2,temp,j;len1=strlen(a)-1;len2=strlen(b)-1;left=0;while(len2>=0){temp=a[len1]-b[len2]+left;if(temp<0){temp+=10;left=-1;}elseleft=0;a[len1]=temp+'0';len1--;len2--;}while(len1>=0){temp=a[len1]-'0'+left;if(temp<0){temp+=10;left=-1;}elseleft=0;a[len1]=temp+'0';len1--;}j=0;while(a[j]=='0') j++;strcpy(a,a+j);if(strlen(a)==0){a[0]='0';a[1]=0;}return; }void sqr(char s[],char re[]) //開方 {char temp[MAXN];char left[MAXN];char p[MAXN];int i,j,k,len1,len2,q;len1=strlen(s);if(len1%2==0){left[0]=s[0];left[1]=s[1];left[2]=0;j=2;}else{left[0]=s[0];left[1]=0;j=1;}re[0]='0';re[1]=0;q=0;while(j<=len1){mul(re,20,temp);len2=strlen(temp);for(i=9;i>=0;i--){temp[len2-1]=i+'0';mul(temp,i,p);if(!big(p,left))break;}re[q++]=i+'0';re[q]=0;sub(left,p);len2=strlen(left);left[len2]=s[j];left[len2+1]=s[j+1];left[len2+2]=0;j+=2;} }int main() {char s[MAXN],s2[MAXN],re[MAXN];int an[MAXN];char ans[MAXN];int i;while(scanf("%s",s)!= EOF ){mul(s,2,s2); //如果是對k*n開方這里就應該是mul(s,k,s2);strcpy(s,s2);re[0]=0;sqr(s,re);i=0;while(re[i]=='0') i++;strcpy(re,re+i);printf("%s\n",re);}return 0; }

?

?

總結

以上是生活随笔為你收集整理的大数开方(C++版)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。