Problem link: https://codeforces.com/problemset/problem/1766/D
Question:
If a number is correct
(
x
,
y
)
(x,y)
(x,y) is lucky if and only if
g
c
d
(
x
,
y
)
=
1
gcd(x,y)=1
gcd(x,y)=1, a chain can be composed of the following regular number pairs,
(
x
,
y
)
,
(
x
+
1
,
y
+
1
)
,
(
x
+
2
,
y
+
2
)
,
…
,
(
x
+
k
,
y
+
k
)
(x,y),(x + 1,y + 1),(x + 2,y + 2),…,(x + k,y + k)
(x,y),(x + 1,y + 1),(x + 2,y + 2),…,(x + k,y + k), if a chain is lucky, if and only if Every number pair in this chain is lucky. Each time a number pair is given, what is the longest length of a lucky chain that can be formed using this number pair as the starting point of a chain? If the length of this chain is infinite, the output
?
1
-1
?1, otherwise the length of the output chain, if the output is unlucky at the beginning
0
0
0.
Ideas:
first
(
1
≤
n
≤
1
0
6
)
(1≤n≤10^6)
(1≤n≤106) if
O
(
n
2
)
O(n^2)
O(n2) will time out. can be found when
y
?
x
=
1
y-x=1
y?x=1 the answer is
?
1
-1
?1 . Then you need to know one
g
c
d
gcd
A conclusion of gcd, when
y
>
x
,
g
c
d
(
x
,
y
)
=
g
c
d
(
x
,
y
?
x
)
y>x,gcd(x,y)=gcd(x,y-x)
y>x,gcd(x,y)=gcd(x,y?x) So the problem is transformed into
g
c
d
(
x
+
i
,
y
?
x
)
gcd(x + i,y-x)
The length of the lucky chain under gcd(x + i,y?x). Then enumerate
y
?
x
y-x
The prime factor of y?x, at this time
O
(
n
?
n
)
O(n*\sqrt n)
O(n?n
y
?
x
y-x
The smallest prime factor of y?x, see
x
x
How many times x
i
i
The arrival of i is the answer, at this time
O
(
n
?
ln
?
n
)
O(n*\ln n)
O(n?lnn).
Code:
#include <bits/setc + + .h>
#define endl '\
'
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
const ll INF_ = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
ll n, m, k, x, y, res = 0, sum = 0, ans = 0, ma = 0, mi = INF;
ll minp[N];
void euler(ll n)
{<!-- -->
bitset<N> vis;
vector<ll> primes;
vis[0] = vis[1] = true;
minp[1] = 1;
for (ll i = 2; i <= n; i + + ) {<!-- -->
if (!vis[i]) primes.push_back(i), minp[i] = i;
for (int j = 0; j < primes.size() & amp; & amp; i * primes[j] <= n; j + + ) {<!-- -->
vis[i * primes[j]] = true;
minp[i * primes[j]] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
void solve()
{<!-- -->
cin >> n;
euler(N);
for (int i = 1; i <= n; i + + ) {<!-- -->
cin >> x >> y;
y -= x;
if (__gcd(x, y) != 1) {<!-- -->
cout << 0 << endl;
continue;
}
if (y == 1) {<!-- -->
cout << -1 << endl;
continue;
}
ans = INF_;
while (y > 1) {<!-- -->
ll p = minp[y];
ans = min(ans, ((-x) % p + p) % p);
while (y % p == 0)
y /= p;
}
cout << ans << endl;
}
}
int main()
{<!-- -->
ios::sync_with_stdio(0);cin.tie(0);
// cout.tie(0);
// ll _;cin>>_;
// while(_--)
solve();
return 0;
}