猫猫与数学【牛客tracker 每日一题】
猫猫与数学
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
猫猫想出了一个数学题，她想考考你。
给定两个正整数a , b a,ba,b，找到最小的整数c ≥ 0 c≥0c≥0，使得g c d ( a + c , b + c ) gcd(a+c,b+c)gcd(a+c,b+c)≠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 c=1c=1时g c d ( 4 , 6 ) = 2 > 1 gcd(4,6)=2>1gcd(4,6)=2>1，这是满足条件的最小的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(1+c,2+c)=gcd(2+c,1)=1gcd(1+c,2+c)=gcd(2+c,1)=1，故无解。
解题思路
本题核心是数论公式化简+因数枚举+最小解计算，解决超大数值范围的公约数问题。利用辗转相除法推导关键公式：gcd ( a + c , b + c ) = gcd ( a + c , ∣ a − b ∣ ) \gcd(a+c,b+c)=\gcd(a+c,|a-b|)gcd(a+c,b+c)=gcd(a+c,∣a−b∣)，设两数差值为d dd。若d = 1 d=1d=1，两数永远互质，直接输出− 1 -1−1；若a = b a=ba=b，则c = 0 c=0c=0即可满足条件。随后枚举d dd的所有大于1的因数，对每个因数p pp，计算让a + c a+ca+c成为p pp倍数的最小非负整数c cc，遍历所有因数后取最小值即为答案。算法通过平方根枚举分解因数，时间复杂度仅O ( d ) O(\sqrt{d})O(d)，完美适配10 14 10^{14}1014的数值范围。
总结
核心逻辑：将原问题化简为求差值的因数，计算最小c cc使a + c a+ca+c被因数整除。
关键操作：数论公式推导、差值因数分解、最小非负解计算。
效率保障：平方根级别的因数枚举，高效处理超大数值，时间空间开销极小。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e5+10;constll INF=0x3f3f3f3f3f3f3f3fLL;constll M=1e6+10;intmain(){ll a,b;cin>>a>>b;if(a==b){cout<<(a==1?1:0);return0;}if(a>=b)swap(a,b);b-=a;ll ans=INF;for(ll i=1;i*i<=b;i++){if(b%i==0){if(i>1){ll t=(a+i-1)/i*i;ans=min(ans,t-a);}ll j=b/i;if(j>1){ll t=(a+j-1)/j*j;ans=min(ans,t-a);}}}cout<<(ans==INF?(-1):ans);return0;}