高精度开方裸题

n 行 m 列的矩阵。

每一个硬币进行一次 Q 操作。

对第x行第y列的硬币进行 Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。

其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。

所有硬币都进行了一次 Q 操作后，所有硬币均为正面朝上。

最开始有多少枚硬币是反面朝上的。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

struct node{int a[1001];};

node getint();

node n,m,ans,p;

node operator *(node k,node t){
node w;
int i,j;
memset(w.a,0,sizeof(w.a));
w.a[0]=k.a[0]+t.a[0]-1;
for(i=1;i<=k.a[0];i++)for(j=1;j<=t.a[0];j++)w.a[i+j-1]+=k.a[i]*t.a[j];
for(i=1;i<=w.a[0];i++){
w.a[i+1]+=w.a[i]/10;
w.a[i]%=10;
if(w.a[w.a[0]+1])w.a[0]++;
}
return w;
}

node operator +(node k,node t){
node w;
int i;
memset(w.a,0,sizeof(w.a));
w.a[0]=max(k.a[0],t.a[0]);
for(i=1;i<=w.a[0];i++)w.a[i]=k.a[i]+t.a[i];
for(i=1;i<=w.a[0];i++){
w.a[i+1]+=w.a[i]/10;
w.a[i]%=10;
}
if(w.a[w.a[0]+1])w.a[0]++;
return w;
}

node qq(node w){
int i;
for(i=w.a[0];i>=1;i--){
if(i>1)w.a[i-1]+=10*(w.a[i]%2);
w.a[i]/=2;
}
if(!w.a[w.a[0]])w.a[0]--;
return w;
}

bool operator <(node k,node t){
int i;
i=max(k.a[0],t.a[0]);
for(;i>=1;i--){
if(k.a[i]<t.a[i])return 1;
if(k.a[i]>t.a[i])return 0;
}
return 1;
}

node operator -(node k,node t){
node w;
int i;
w=k;
w.a[1]-=t.a[1];
for(i=1;w.a[i]<0;i++){
w.a[i+1]--;
w.a[i]+=10;
}
if(!w.a[w.a[0]])w.a[0]--;
return w;
}

bool pd(node k,node t){
if(k.a[0]!=t.a[0])return 1;
int i;
for(i=1;i<=k.a[0];i++)if(k.a[i]!=t.a[i])return 1;
return 0;
}

node xx(node l,node r,node x){
node mid;
while(pd(l,r)){
mid=qq(l+r)+p;
if(mid*mid<x)l=mid;
else r=mid-p;
}
return l;
}

int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
n=getint();m=getint();
p.a[0]=p.a[1]=1;
ans=xx(p,n,n)*xx(p,m,m);
for(int i=ans.a[0];i>=1;i--)printf("%d",ans.a[i]);
return 0;
}

node getint(){
node w;
w.a[0]=0;
char c=getchar();
while(c>‘9‘||c<‘0‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘)w.a[++w.a[0]]=c-‘0‘,c=getchar();
for(int i=1;i<=w.a[0]/2;i++)swap(w.a[i],w.a[w.a[0]-i+1]);
return w;
}

高精度开方裸题

原文：http://www.cnblogs.com/lqx123/p/6444738.html