大数处理
发布时间:2020-12-14 03:01:13 所属栏目:大数据 来源:网络整理
导读:p style="color: rgb(51,51); font-family: Arial; font-size: 14px; line-height: 26px;"题意:给定一个长方形,将该长方形切分成几个面积相等且边最大的正方形,求这样的正方形的最大边长,难点在于长方形边长为二进制形式,输出的正方形边长也为二进制,
<p style="color: rgb(51,51); font-family: Arial; font-size: 14px; line-height: 26px;">题意:给定一个长方形,将该长方形切分成几个面积相等且边最大的正方形,求这样的正方形的最大边长,难点在于长方形边长为二进制形式,输出的正方形边长也为二进制,另外该题数据量巨大2^1000。</p><p style="color: rgb(51,51); font-family: Arial; font-size: 14px; line-height: 26px;">解题思路:由于该题数据量巨大,所以要用到大数处理方法,不过不用担心,对于大数有专门的模板,可以说这道题是模板题,直接看代码吧。</p> #include <iostream> #include <cstdio> #include <cstring> #define MAXN 1000 using namespace std; struct BigNumber{ int len; int v[MAXN]; }; bool isSmaller(BigNumber n1,BigNumber n2) { if(n1.len<n2.len) return 1; if(n1.len>n2.len) return 0; for(int i=n1.len-1;i>=0;i--) { if(n1.v[i]<n2.v[i]) return 1; if(n1.v[i]>n2.v[i]) return 0; } return 0; } BigNumber Minus(BigNumber n1,BigNumber n2) { BigNumber ret; int borrow,i,temp; ret=n1; for(borrow=0,i=0;i<n2.len;i++) { temp=ret.v[i]-borrow-n2.v[i]; if(temp>=0) { borrow=0; ret.v[i]=temp; } else { borrow=1; ret.v[i]=temp+2; } } for(;i<n1.len;i++) { temp=ret.v[i]-borrow; if(temp>=0) { borrow=0; ret.v[i]=temp; } else { borrow=1; ret.v[i]=temp+2; } } while(ret.len>=1 && !ret.v[ret.len-1]) ret.len--; return ret; } BigNumber div2(BigNumber n) { BigNumber ret; ret.len=n.len-1; for(int i=0;i<ret.len;i++) ret.v[i]=n.v[i+1]; return ret; } void gcd(BigNumber n1,BigNumber n2,int j) { long b=0,i; while(n1.len && n2.len) { if(n1.v[0]) { if(n2.v[0]) { if(isSmaller(n1,n2)) n2 = Minus(n2,n1); else n1 = Minus(n1,n2); } else n2=div2(n2); } else { if(n2.v[0]) n1=div2(n1); else { n1=div2(n1); n2=div2(n2); b++; } } } printf("Case #%d: ",j); if(n2.len) for(i=n2.len-1;i>=0;i--) printf("%d",n2.v[i]); else for(i=n1.len-1;i>=0;i--) printf("%d",n1.v[i]); while(b--) printf("0"); printf("n"); } int main() { int cases,le,i; BigNumber n1,n2; char str1[MAXN],str2[MAXN]; scanf("%d",&cases); for(int j = 1; j <= cases; j++) { scanf("%s%s",str1,str2); le=strlen(str1); n1.len=le; for(i=0;i<le;i++) n1.v[i]=str1[le-1-i]-'0'; le=strlen(str2); n2.len=le; for(i=0;i<le;i++) n2.v[i]=str2[le-1-i]-'0'; gcd(n1,n2,j); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |