526互联

Educational Codeforces Round 139 (Rated for Div. 2) D. Lucky Chains（数论）

发布时间 2023-12-16 21:35:39作者: ikunhuaji
Educational Codeforces Round 139 (Rated for Div. 2) D. Lucky Chains

思路：

假设幸运为k ， 则 gcd(x+k,y+k) ≠ 1 , k取最小整数（k>=0）

由此可设 因子为 d ， (x+k)%d = 0 , (y+k)%d = 0

因此 (y-x)%d = 0; 我们只需遍历 y-x 的所有质因子

对于这些质因子，找到大于等于 x 的最小倍数

答案即为 ((x + d - 1) / d) * d 取最小

#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);

using namespace std;

const int N = 1e7 + 10,INF=1e9;

int pr[N];
bool st[N];
int n, cnt, m;
int sum1[N], d[N];// d 用于存储 i 的最小质因子
vector<int>as;

void p(int x) {//线性筛
    for (int i = 2; i <= x; i++)
    {
        if (!st[i])pr[cnt++] = i, d[i] = i;
        for (int j = 0; pr[j] <= x / i; j++)
        {
            st[pr[j] * i] = true;
            d[pr[j] * i] = pr[j];
            if (i % pr[j] == 0)break;
        }
    }
}

void getpr(int v)
{
    while (v > 1)
    {
        if (as.empty() || as.back() != d[v])as.pb(d[v]);

        v /= d[v];
    }
}

void solve()
{
    int a, b;
    cin >> a >> b;

    int s = b - a;

    if (s == 1)
    {
        cout << -1 << endl;
        return;
    }
    as.clear();

    getpr(s);

    int ans = INF;
    for (int it : as)
    {
        ans = min(ans, ((a + it - 1) / it) * it);
    }
    cout << ans-a << endl;
}

signed main()
{
    ikun;

    p(N - 1);

    int t;
    t == 1;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}