题解 | 猫猫与数学

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;


vector<ll> get(ll n)
{
    vector<ll> factors;
    if(n%2==0)
    {
        factors.push_back(2);
        while(n%2==0)
        n/=2;
    }
    for(ll i=3;i*i<=n;i+=2)
    {
        if(n%i==0)
        {
            factors.push_back(i);
            while(n%i==0)
            n/=i;
        }
    }
    if(n>1)
    factors.push_back(n);
    return factors;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll a,b;
    cin>>a>>b;
    ll c;
    ll mini=1e18;
    ll d=abs(b-a);
    if(a==b)
    {
        if(a==1)
        {
            cout<<1;
        }
        else
        cout<<0;
    } 
    else if(d==1)
    {
        cout<<"-1";
    }
    else if(d>1)
    {
        bool flag=0;
        vector<ll> primes=get(d);
        for(int i=0;i<primes.size();i++)
        {
            ll p=primes[i];
            if(a%p==0)
            {
                flag=1;
                cout<<"0";
                break;
            }
            else
            {
                c=p-(a%p);
                mini=min(mini,c);
            }
        }
        if(flag==0)
        cout<<mini;
    }
    return 0;
}

本题考查辗转相除法与质因数分解，重点是根据样例中的提示想到利用辗转相除法的性质推出gcd(a+c,b+c)=gcd(a+c,|a-b|)这一条件，设d=|a-b|，从而转化为a,c与d之间的关系，进而简化思路。

注意：

1. 数据范围较大，开ll；
2. 特殊情况判断；

补充：

1.辗转相除法：

gcd(x, y)=gcd(y, x−y)；

即把较大的数减去较小的数，最大公约数不变

所以：

gcd(x, y)=gcd(y, xmody)；

2.质因数分解：get数组预处理