小红的数位删除时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了两个正整数a aa和b bb她每次操作可以选择其中一个正整数删除一个数位。例如对于 1243 12431243而言进行一次操作可以生成 124 、 123 、 143 124、123、143124、123、143或 243 243243。小红希望最终a aa是b bb的倍数或者b bb是a aa的倍数。她想知道自己最少的操作次数是多少输入描述两个正整数a aa和b bb用空格隔开。1 ≤ a , b ≤ 10 9 1≤a,b≤10^91≤a,b≤109输出描述如果无法如何都无法使得a aa是b bb的倍数或者b bb是a aa的倍数则输出− 1 -1−1。否则输出一个整数代表小红的最小操作次数。示例1输入37 111输出0说明111 111111是37 3737的倍数所以小红不需要任何操作。示例2输入1234 99输出2说明第一个数删除数字′ 1 ′ 1′1′变成234 234234。第二个数删除数字′ 9 ′ 9′9′变成9 99。234 234234是9 99的倍数。解题思路本题采用二进制枚举暴力验证的思路求解最小操作次数核心是用二进制位掩码枚举a 、 b a、ba、b所有可能的数位保留/删除组合将a aa的每一位对应二进制数的一个比特位1 11保留、0 00删除同理处理b bb遍历a aa的所有掩码共2 n 2^n2n种和b bb的所有掩码共2 m 2^m2m种计算每种组合下保留的数字x xxa aa的保留数位组成、y yyb bb的保留数位组成及操作次数o p opop删除的数位总数过滤掉x xx或y yy为0 00的无效情况若x xx是y yy的倍数或y yy是x xx的倍数则更新最小操作次数a n s ansans最终若a n s ansans仍为无穷大则输出− 1 -1−1否则输出a n s ansans。该方法通过枚举所有可能的数位删除组合暴力验证是否满足倍数条件虽时间复杂度较高但因a 、 b a、ba、b位数最多为10 1010位2 1 0 1024 2^1010242101024实际可高效运行精准找到满足条件的最小操作次数。总结核心逻辑是用二进制掩码枚举a 、 b a、ba、b所有数位保留/删除组合计算对应保留数字和操作次数。关键验证条件保留数字非0 00且满足倍数关系更新最小操作次数。最终根据最小操作次数是否为无穷大输出− 1 -1−1或具体数值。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N2e510;constll inf0x3f3f3f3f3f3f3f3f;intmain(){string a,b;cinab;ll ansinf;ll na.size(),mb.size();for(ll i0;i(1n);i){for(ll j0;j(1m);j){ll op0,x0,y0;for(ll k0;kn;k){if(i(1k))xx*10a[k]-0;elseop;}for(ll k0;km;k){if(j(1k))yy*10b[k]-0;elseop;}if(!x||!y)continue;if(x%y0||y%x0)ansmin(ans,op);}}cout(ansinf?-1:ans)endl;return0;}