[hud-6646]A+B=C 高精度大数思维 2019多校7

本是古典何须时尚 2021-07-26 02:40 151阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6646][http_acm.hdu.edu.cn_showproblem.php_pid_6646]

题目大意： a\*10^x +  b\*10^y  = c\*10^z   给a、b、c   求 x、y、z

a、b、c<10^100000  如果没有满足的x.y.z 输出-1

题解：

plana： 把a,b,c都末尾加0补到相同长度得到a0,b0,c0  末尾都去掉0得到a1,b1,c1  
定义cmp( x,y )==1 为x和y的前半非零部分完全相同  
这时只有四种情况  
①cmp( c0-a0, b1)      即c0-a0 得到的部分，前半非0部分和b1相同  
②cmp( c0\*10-a0 , b1 )  即c0乘10减a0，得到的部分前面非0部分和b1相同  
③cmp( c0-b0, a1)  
④cmp( c0\*10-b0 , a1 )

都不满足就不存在  
注意每一次a、b、c由字符串转为数字前都要把数字数组memset为0

![1606447-20190816120513657-2062869528.jpg][]

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 int const maxn=1e5+100;
      4 char a[maxn],b[maxn],c[maxn];
      5 int lena,lenb,lenc,tmpa,tmpb,tmpc,ansa,ansb,ansc,maxlen;
      6 bool flag;
      7 int an[maxn],bn[maxn],cn[maxn],adn[maxn];
      8 void innum2(int aa[],char x[],int z,int tmp,int zer){
        //数字字符串x，去掉末尾0后为z位数，zer后面要补0的个数
      9     //memset(aa,0,sizeof(aa));
     10     aa[0]=z;
     11     for(int i=1;i<=zer;i++)aa[i]=0;
     12     for(int i=1;i<=aa[0];i++)
     13       aa[i+zer]=x[aa[0]-i]-48;
     14     aa[0]+=zer;
     15 }
     16 void jian(int a[],int b[]){
     17     for(int i=a[0];i>0;i--)a[i]-=b[i];
     18     for(int i=1;i<=a[0];i++)
     19         if(a[i]<0){
     20             a[i]+=10;
     21             a[i+1]--;
     22         }
     23     while(a[a[0]]==0)a[0]--;
     24 }
     25 int maxme(int x,int y,int z){
     26     if(x<y)swap(x,y);
     27     if(x<z)swap(x,z);
     28     return x;
     29 }
     30 int minme(int x,int y,int z){
     31     if(x>y)swap(x,y);
     32     if(x>z)swap(x,z);
     33     return x;
     34 }
     35 void pushans(int x,int y,int z){
     36     int v=minme(x,y,z);
     37     if(v<0){ansa=x-v,ansb=y-v,ansc=z-v;}
     38     else {ansa=x,ansb=y,ansc=z;}
     39     flag=1;
     40 }
     41 bool cmp(int x[],int y[]){
     42     if(x[0]<y[0])return 0;
     43     bool vis3=1;
     44     for(int i=0;i<y[0];i++){
     45         if(y[y[0]-i]!=x[x[0]-i]){vis3=0;break;}
     46     }
     47     return vis3;
     48 }
     49 void work(){
     50     memset(cn,0,sizeof cn);memset(an,0,sizeof an);memset(bn,0,sizeof bn);
     51     innum2(cn,c,lenc,tmpc,maxlen-lenc);
     52     innum2(an,a,lena,tmpa,maxlen-lena);
     53     innum2(bn,b,lenb,tmpb,0);
     54     jian(cn,an);
     55     if(cmp(cn,bn)){
     56         pushans(maxlen-lena-tmpa,cn[0]-lenb-tmpb,maxlen-lenc-tmpc);return ;
     57     }
     58     memset(cn,0,sizeof cn);
     59     innum2(cn,c,lenc,tmpc,maxlen-lenc+1);
     60     jian(cn,an);
     61     if(cmp(cn,bn)){
     62         pushans(maxlen-lena-tmpa,cn[0]-lenb-tmpb,maxlen-lenc+1-tmpc);return ;
     63     }
     64     memset(cn,0,sizeof cn);memset(an,0,sizeof an);memset(bn,0,sizeof bn);
     65     innum2(cn,c,lenc,tmpc,maxlen-lenc);
     66     innum2(bn,b,lenb,tmpb,maxlen-lenb);
     67     innum2(an,a,lena,tmpa,0);
     68     jian(cn,bn);
     69     if(cmp(cn,an)){
     70         pushans(cn[0]-lena-tmpa,maxlen-lenb-tmpb,maxlen-lenc-tmpc);return ;
     71     }
     72     memset(cn,0,sizeof cn);
     73     innum2(cn,c,lenc,tmpc,maxlen-lenc+1);
     74     jian(cn,bn);
     75     if(cmp(cn,an)){
     76         pushans(cn[0]-lena-tmpa,maxlen-lenb-tmpb,maxlen-lenc+1-tmpc);return ;
     77     }
     78 }
     79 int main()
     80 {
     81     int t;
     82     scanf("%d",&t);
     83     while(t--){
     84         tmpa=tmpb=tmpc=0;
     85         flag=0;
     86         scanf("%s%s%s",a,b,c);
     87         lena=strlen(a),lenb=strlen(b),lenc=strlen(c);
     88         maxlen=maxme(lena,lenb,lenc);
     89         while(a[lena-1]==48)tmpa++,lena--;
     90         while(b[lenb-1]==48)tmpb++,lenb--;
     91         while(c[lenc-1]==48)tmpc++,lenc--;
     92         work();
     93         
     94         if(flag){    
     95             printf("%d %d %d\n",ansa,ansb,ansc);    
     96         }
     97         else
     98         printf("-1\n");
     99     }
    100     return 0;    
    101 }

*10x\+b⋅10y=c⋅10*

转载于:https://www.cnblogs.com/conver/p/11363094.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6646]: http://acm.hdu.edu.cn/showproblem.php?pid=6646
[1606447-20190816120513657-2062869528.jpg]: /images/20210725/0f71cf04d9864b67821fff335e67278e.png