题目

AC 代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main() 
{
    ll a, b;
    cin>>a>>b;

    ll d=abs(a-b);
    if(d==0)
    {
        if(a==1)
          cout<<1<<endl;
        else
          cout<<0<<endl;
        return 0;
    }

    if(d==1)cout<<-1<<endl;
    else
    {
        vector<ll> v;
        for(ll i=2;i*i<=d;i++)
        {
            if(d%i==0)
            {
                v.push_back(i);
                while(d%i==0)
                {
                    d=d/i;
                }
            }
        }
        if(d>1)v.push_back(d);

        ll ans = 1e18;
        for(auto& x:v)
        {
            ans=min(ans,(x-a%x)%x);
        }
        cout<<ans<<endl;
    }

    return 0;
}

个人见解

由题意，假设有一数字 ，令 ，我们希望得到 和 ，即 整除 和 整除 ，因此有：

if(d==0)
{
    if(a==1)
      cout<<1<<endl;
    else
      cout<<0<<endl;
    return 0;
}

这里的判断需要小心 的情况，此时只需要 即可让 变成 。

if(d==1)cout<<-1<<endl;
else
{
    vector<ll> v;
    for(ll i=2;i*i<=d;i++)
    {
        if(d%i==0)
        {
            v.push_back(i);
            while(d%i==0)
            {
                d=d/i;
            }
        }
    }
    if(d>1)v.push_back(d);

    ll ans = 1e18;
    for(auto& x:v)
    {
        ans=min(ans,(x-a%x)%x);
    }
    cout<<ans<<endl;
}

这是代码的核心部分，如果 当然直接输出 。否则，需要循环寻找 的因子，与普通寻找因数不同的是，本题只需要存储质因子，因为我们只想找到最小的 和 。

if(d%i==0)
{
    v.push_back(i);
    while(d%i==0)
    {
        d=d/i;
    }
}

因此，只要 就直接推入 vector 容器，然后利用 循环剔除所有因子 ，这也是在保证往后出现的 一定是质因子的原因。

if(d>1)v.push_back(d); 

因为 的值在变化，可能会出现 但是 的情况，如果不加这行会遗漏关键的一个质因子！！！

ll ans = 1e18;
for(auto& x:v)
{
    ans=min(ans,(x-a%x)%x);
}

这里就是在寻找最小 的过程了，注意这里的表达式 。 表示 大出 的数值，而 表示距离凑出下一个 的倍数需要补齐的数字，那么为什么要再对 取模呢？举个例子，如果 ，此时 ，但真实情况是由于 可以整除 ，所以 此时不需要补齐任何数字，因此最后再对 进行取模，即 。