[cpp]
描述：這道題雖然是開方題，可是數據量卻相當的大，可達1000位，不得不用大數來做
#include <cstdio>
#include <cstring>
int n,m,flag,t;
char s[1010],v[1010];
int sum[1010],p[1010];
int l_sum,l_p;
bool com()
{
for(int i=0; i<l_sum; ++i)
if(sum[i]>p[i]) return 0;
else if(sum[i]<p[i])return 1;
else continue;
return 1;
}
void sub()
{
int flag=-1,len=l_sum-1;
for(int i=l_p-1; i>=0; --i)
{
if(p[i]>=sum[len]) p[i]-=sum[len];
else
{
for(int j=i-1; j>=0; --j)
if(p[j])
{
--p[j];
for(int k=j+1; k<i; ++k) p[k]=99;
break;
}
p[i]=p[i]+100-sum[len];
}
--len;
if(len<0) break;
}
for(flag=0; flag<l_p; ++flag)
if(p[flag]>0) break;
if(flag>0)
{
len=0;
for(int i=flag; i<l_p; ++i) p[len++]=p[i];
l_p=len;
}
}
void add()
{
int flag=2;
for(int i=l_sum-1; i>=0; --i)
if(sum[i]+flag>99)
{
s[i]=(s[i]+flag)%100;
flag=1;
}
else
{
sum[i]+=flag;
return;
}
for(int i=l_sum; i>=1; --i)
sum[i]=sum[i-1];
sum[0]=flag;
++l_sum;
}
void solve()
{
int flag=0,c=0;
for(int i=l_sum-1; i>=0; --i)
{
c=(sum[i]*10+flag)/100;
sum[i]=(sum[i]*10+flag)%100;
flag=c;
}
if(flag>0)
{
for(int i=l_sum; i>=1; --i) sum[i]=sum[i-1];
sum[0]=flag;
++l_sum;
}
c=9;
int i=l_sum-1;
if(sum[i]<c)
{
for(int j=i-1; j>=0; --j)
if(sum[j])
{
--sum[j];
for(int k=j+1; k<i; ++k) sum[k]=99;
sum[i]=sum[i]+100-c;
break;
}
}
else sum[i]-=c;
if(sum[0]<=0)
{
for(i=1; i<l_sum; ++i) sum[i-1]=sum[i];
--l_sum;
}
}
void che()
{
int flag=0;
for( ; flag<l_p; ++flag)
if(p[flag]>0) break;
if(flag>0)
{
int len=0;
for(int i=flag; i<l_p; ++i) p[len++]=p[i];
l_p=len;
}
}
int main()
{
// freopen("a.txt","r",stdin);
// freopen("c.txt","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
n=strlen(s);
m=0;
l_p=l_sum=sum[0]=1;
int i;
if(n%2==1) p[0]=s[0]-'0',i=1;
else p[0]=(s[0]-'0')*10+s[1]-'0',i=2;
while(1)
{
v[m]='0';
while(1)
{
if(l_p>l_sum||(l_p==l_sum&&com()))
{
sub();
v[m]++;
add();
}
else break;
}
che();
v[++m]=0;
if(i+1<n)
{
p[l_p++]=(s[i]-'0')*10+s[i+1]-'0';
i+=2;
}
else break;
solve();
}
puts(v);
if(t) puts("");
}
return 0;
}
描述：這道題雖然是開方題，可是數據量卻相當的大，可達1000位，不得不用大數來做
#include <cstdio>
#include <cstring>
int n,m,flag,t;
char s[1010],v[1010];
int sum[1010],p[1010];
int l_sum,l_p;
bool com()
{
for(int i=0; i<l_sum; ++i)
if(sum[i]>p[i]) return 0;
else if(sum[i]<p[i])return 1;
else continue;
return 1;
}
void sub()
{
int flag=-1,len=l_sum-1;
for(int i=l_p-1; i>=0; --i)
{
if(p[i]>=sum[len]) p[i]-=sum[len];
else
{
for(int j=i-1; j>=0; --j)
if(p[j])
{
--p[j];
for(int k=j+1; k<i; ++k) p[k]=99;
break;
}
p[i]=p[i]+100-sum[len];
}
--len;
if(len<0) break;
}
for(flag=0; flag<l_p; ++flag)
if(p[flag]>0) break;
if(flag>0)
{
len=0;
for(int i=flag; i<l_p; ++i) p[len++]=p[i];
l_p=len;
}
}
void add()
{
int flag=2;
for(int i=l_sum-1; i>=0; --i)
if(sum[i]+flag>99)
{
s[i]=(s[i]+flag)%100;
flag=1;
}
else
{
sum[i]+=flag;
return;
}
for(int i=l_sum; i>=1; --i)
sum[i]=sum[i-1];
sum[0]=flag;
++l_sum;
}
void solve()
{
int flag=0,c=0;
for(int i=l_sum-1; i>=0; --i)
{
c=(sum[i]*10+flag)/100;
sum[i]=(sum[i]*10+flag)%100;
flag=c;
}
if(flag>0)
{
for(int i=l_sum; i>=1; --i) sum[i]=sum[i-1];
sum[0]=flag;
++l_sum;
}
c=9;
int i=l_sum-1;
if(sum[i]<c)
{
for(int j=i-1; j>=0; --j)
if(sum[j])
{
--sum[j];
for(int k=j+1; k<i; ++k) sum[k]=99;
sum[i]=sum[i]+100-c;
break;
}
}
else sum[i]-=c;
if(sum[0]<=0)
{
for(i=1; i<l_sum; ++i) sum[i-1]=sum[i];
--l_sum;
}
}
void che()
{
int flag=0;
for( ; flag<l_p; ++flag)
if(p[flag]>0) break;
if(flag>0)
{
int len=0;
for(int i=flag; i<l_p; ++i) p[len++]=p[i];
l_p=len;
}
}
int main()
{
// freopen("a.txt","r",stdin);
// freopen("c.txt","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
n=strlen(s);
m=0;
l_p=l_sum=sum[0]=1;
int i;
if(n%2==1) p[0]=s[0]-'0',i=1;
else p[0]=(s[0]-'0')*10+s[1]-'0',i=2;
while(1)
{
v[m]='0';
while(1)
{
if(l_p>l_sum||(l_p==l_sum&&com()))
{
sub();
v[m]++;
add();
}
else break;
}
che();
v[++m]=0;
if(i+1<n)
{
p[l_p++]=(s[i]-'0')*10+s[i+1]-'0';
i+=2;
}
else break;
solve();
}
puts(v);
if(t) puts("");
}
return 0;
}
