猫猫与数学时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述猫猫想出了一个数学题她想考考你。给定两个正整数a , b a,ba,b找到最小的整数c ≥ 0 c≥0c≥0使得g c d ⁡ ( a c , b c ) gcd⁡(ac,bc)gcd⁡(ac,bc)̸1 11。此处 gcd 表示最大公约数。如果无解输出− 1 −1−1。输入描述一行两个正整数a , b a,ba,b。1 ≤ a , b ≤ 10 14 1≤a,b≤10^{14}1≤a,b≤1014。输出描述一行一个整数表示最小的c cc。无解输出− 1 −1−1。示例1输入3 5输出1说明c 1 c1c1时g c d ⁡ ( 4 , 6 ) 2 1 gcd⁡(4,6)21gcd⁡(4,6)21这是满足条件的最小的c cc。示例2输入1 2输出-1说明对于任意c ≥ 0 c≥0c≥0根据辗转相除法g c d ⁡ ( 1 c , 2 c ) g c d ⁡ ( 2 c , 1 ) 1 gcd⁡(1c,2c)gcd⁡(2c,1)1gcd⁡(1c,2c)gcd⁡(2c,1)1故无解。解题思路本题核心是数论公式化简因数枚举最小解计算解决超大数值范围的公约数问题。利用辗转相除法推导关键公式gcd ⁡ ( a c , b c ) gcd ⁡ ( a c , ∣ a − b ∣ ) \gcd(ac,bc)\gcd(ac,|a-b|)gcd(ac,bc)gcd(ac,∣a−b∣)设两数差值为d dd。若d 1 d1d1两数永远互质直接输出− 1 -1−1若a b abab则c 0 c0c0即可满足条件。随后枚举d dd的所有大于1的因数对每个因数p pp计算让a c acac成为p pp倍数的最小非负整数c cc遍历所有因数后取最小值即为答案。算法通过平方根枚举分解因数时间复杂度仅O ( d ) O(\sqrt{d})O(d​)完美适配10 14 10^{14}1014的数值范围。总结核心逻辑将原问题化简为求差值的因数计算最小c cc使a c acac被因数整除。关键操作数论公式推导、差值因数分解、最小非负解计算。效率保障平方根级别的因数枚举高效处理超大数值时间空间开销极小。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e510;constll INF0x3f3f3f3f3f3f3f3fLL;constll M1e610;intmain(){ll a,b;cinab;if(ab){cout(a1?1:0);return0;}if(ab)swap(a,b);b-a;ll ansINF;for(ll i1;i*ib;i){if(b%i0){if(i1){ll t(ai-1)/i*i;ansmin(ans,t-a);}ll jb/i;if(j1){ll t(aj-1)/j*j;ansmin(ans,t-a);}}}cout(ansINF?(-1):ans);return0;}