大数平方
#include<stdio.h> #include<string.h> #include<math.h> int 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; } else left=0; a[len1]=temp+'0'; len1--; len2--; } while(len1>=0) { temp=a[len1]-'0'+left; if(temp<0) { temp+=10; left=-1; } else left=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[1010]; char left[1010]; char p[1010]; 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; } } char s[2010],re[2010]; int num[2010],len; void div2() { int i; for (i=len-1;i>=0;i--) { if ((num[i]&1)&&i) { num[i-1]+=10; } num[i]>>=1; } if (num[len-1]==0) len--;//1000000000000 } void println() { int b=0; int two=2; int digits[2010]; int p=0; while(len) { if(num[0]&1) digits[p++]=1; else digits[p++]=0; div2(); } int i; for (i=p-1;i>=0;i--) printf("%d",digits[i]); puts(""); } int main() { while(scanf("%s",s)!=EOF) { if(strcmp(s,"0")==0) { printf("0/n"); continue; } if(strcmp(s,"#")==0) break; re[0]=0; sqr(s,re); int i=0; while(re[i]=='0') i++; strcpy(re,re+i); int l=strlen(re); len=0; int p=l; for(int i=0;i<l;i++) num[--p]=re[i]-'0',len++; println(); } }