CF1766题解

Huami360 · 2022-12-14 20:19:20 · 题解

这题作为D算简单的了，由更相减损术知 \gcd(a,b)=\gcd(a,b-a)，于是只要在a以上找到第一个和b-a公因数不为一的数即可，可以直接线筛出1e7内所有数的质因数，然后暴力找最小即可。

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define pb push_back
#define rep(i, m, n) for(int i = (m); i <= (n); ++i)
#define dop(i, m, n) for(int i = (m); i >= (n); --i)
#define all(x) x.begin(), x.end()
#define Open(s) freopen(s,"r",stdin);
#define Write(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
template <class T> void chkmin(T &a, T b){ if(a > b) a = b; }
template <class T> void chkmax(T &a, T b){ if(a < b) a = b; }
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<PII> VII;
const int N = 1e7 + 10;
int n;
int a, b;
int v[N], prime[1000000], cnt;
int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}
//vector <int> p[N];
struct edge{
    int next, to;
}e[N * 4];
int head[N], num;
inline void add(int x, int y){
    e[++num].to = y;
    e[num].next = head[x];
    head[x] = num;
}
inline void solve(){
    scanf("%d%d", &a, &b);
    if(gcd(a, b) != 1) puts("0");
    else if(a == b && a == 1) puts("1");
    else if(b - a == 1 || a - b == 1) puts("-1");
    else{
        if(a > b) swap(a, b);
        int ans = 2147483647;
        for(int i = head[b-a]; i; i = e[i].next)
            chkmin(ans, e[i].to - a % e[i].to);
        printf("%d\n", ans);
    }
}
int T;
int main(){
    rep(i, 2, 10000000){
       if(!v[i]){
         v[i] = i;
         prime[++cnt] = i;
       }
       rep(j, 1, cnt){
          if(v[i] < prime[j] || prime[j] * i > 10000000) break;
          v[i * prime[j]] = prime[j];
       }
    }
    rep(i, 1, cnt)
        for(int j = prime[i]; j <= 10000000; j += prime[i])
            add(j, prime[i]);
    scanf("%d", &T);
    while(T--){
        //printf("%s\n", solve() ? "YES" : "NO");
        //printf("%d\n", solve());
        solve();
    }
    //solve();
    return 0;
}