/>

题目描述

小红拿到了两个正整数a

aa和b

bb，她每次操作可以选择其中一个正整数，删除一个数位。

例如，对于"

1243

"1243""1243"而言，进行一次操作可以生成"

124

"124"、"123"、"143""124"、"123"、"143"或"

243

"243""243"。

aa是b

bb的倍数或者b

bb是a

aa的倍数。

她想知道自己最少的操作次数是多少？

输入描述：

两个正整数a

aa和b

bb，用空格隔开。

1≤a,b≤10^91≤a,b≤10

style="height:

0.05em;">9

输出描述：

如果无法如何都无法使得a

aa是b

bb的倍数或者b

bb是a

aa的倍数，则输出−

-1−1。

/>否则输出一个整数，代表小红的最小操作次数。

示例1

输入：

37
111

输出：

0

说明：

111

111111是37

3737的倍数，所以小红不需要任何操作。

示例2

输入：

1234
99

输出：

2

说明：

第一个数删除数字′

'1'

style="height:

0.05em;">′1

style="height:

0.05em;">′，变成234

234234。

第二个数删除数字′

'9'

style="height:

0.05em;">′9

style="height:

0.05em;">′，变成9

99。

234

234234是9

99的倍数。

解题思路

本题采用二进制枚举+暴力验证的思路求解最小操作次数，核心是用二进制位掩码枚举a

a、ba、b所有可能的数位保留/删除组合：将a

aa的每一位对应二进制数的一个比特位（1

11保留、0

00删除），同理处理b

bb；遍历a

aa的所有掩码（共2

2^n2

style="height:

0.05em;">n种）和b

bb的所有掩码（共2

2^m2

style="height:

0.05em;">m种），计算每种组合下保留的数字x

xx（a

aa的保留数位组成）、y

style="margin-right:

0.0359em;">y（b

bb的保留数位组成）及操作次数o

opop（删除的数位总数）；过滤掉x

xx或y

style="margin-right:

0.0359em;">y为0

00的无效情况，若x

xx是y

style="margin-right:

0.0359em;">y的倍数或y

style="margin-right:

0.0359em;">y是x

xx的倍数，则更新最小操作次数a

ansans；最终若a

ansans仍为无穷大则输出−

-1−1，否则输出a

ansans。

该方法通过枚举所有可能的数位删除组合，暴力验证是否满足倍数条件，虽时间复杂度较高，但因a

a、ba、b位数最多为10

1010位（2

=

2^10=10242

style="height:

0.05em;">10=1024），实际可高效运行，精准找到满足条件的最小操作次数。

总结

1. 核心逻辑是用二进制掩码枚举a

   a、ba、b所有数位保留/删除组合，计算对应保留数字和操作次数。

2. 关键验证条件：保留数字非0

   00且满足倍数关系，更新最小操作次数。

3. 最终根据最小操作次数是否为无穷大，输出−

   -1−1或具体数值。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll
p=1e9+7;constll
N=2e5+10;constll
inf=0x3f3f3f3f3f3f3f3f;intmain(){string
a,b;cin>>a>>b;ll
ans=inf;ll
n=a.size(),m=b.size();for(ll
i=0;i<(1<<n);i++){for(ll
j=0;j<(1<<m);j++){ll
op=0,x=0,y=0;for(ll
k=0;k<n;k++){if(i&(1<<k))x=x*10+a[k]-'0';elseop++;}for(ll
k=0;k<m;k++){if(j&(1<<k))y=y*10+b[k]-'0';elseop++;}if(!x||!y)continue;if(x%y==0||y%x==0)ans=min(ans,op);}}cout<<(ans==inf?-1:ans)<<endl;return0;}