Given two integers n and m. Discover the variety of steady pairs attainable with gcd(n, m) = 1, whereby every step 1 may be incremented to the pair.
Examples:
Enter: n = 1, m = 4
Output: 2
Rationalization: gcd(1, 4) =1, within the subsequent step gcd(2, 5) =1 so the utmost attainable steady pairs are 2.Enter: n = 5, m = 13
Output:1
Rationalization: Solely that pair is feasible with gcd(n, m) =1 as a result of within the subsequent step n = 6, m = 14 which has gcd = 2 so the output is 1.
Strategy: This may be solved with the under thought:
We have to discover the ok such that gcd(n+ok, m+ok) is bigger than 2, so there must be at the very least 1 prime quantity that divides each n+ok, and m+ok, excluding distinctive circumstances when n=m and n = m+1. There must be a quantity p that divides each m+ok and n+ok.
Therefore the distinction (n-m) % p = 0, so we solely want to have a look at prime components of n-m such that n+ok % p =0 so we take the minimal worth of p – npercentp which is the variety of steps it may be incremented in order that gcd (n, m) is 1.
Observe the steps talked about under to unravel the issue:
- Construct the sieve to retailer the smallest prime components
- Discover the present gcd and if the preliminary gcd shouldn’t be equal to 1 then return 0.
- Swap n, m if n > m
- Discover the distinction and examine if the distinction is 1, If the distinction is 1 return -1 since gcd might be 1 for infinite steps
- Discover all of the prime components of the distinction utilizing factorize operate.
- Initialize the variable pairs to search out the variety of steady pairs
- Iterate by the prime components and examine the pairs which can be attainable by taking a minimal of p-npercentp. Return the variety of pairs
Under is the implementation of the above strategy:
C++
// C++ code for the above strategy
#embody <bits/stdc++.h>
utilizing namespace std;
int N = 10000005;
vector<lengthy lengthy> spf(N + 1, 1);
// Construct the sieve to retailer
// smallest prime components
void build_sieve()
{
lengthy lengthy i, j;
for (i = 2; i < N; i++) {
if (spf[i] == 1) {
spf[i] = i;
for (j = i * i; j <= N; j += i) {
if (spf[j] == 1)
spf[j] = i;
}
}
}
}
// Perform to get the prime
// issue of the quantity n
vector<int> factorize(int n)
{
vector<int> ans;
whereas (n > 1) {
int truth = spf[n];
whereas (n % truth == 0) {
n /= truth;
}
ans.push_back(truth);
}
return ans;
}
// Perform to search out the utmost
// attainable steady pairs
int find_maxpairs(int n, int m)
{
// Calling the build_sieve
build_sieve();
// Discover the present gcd and if preliminary
// gcd shouldn't be equal to 1 then return 0.
int gcd = __gcd(n, m);
if (gcd != 1) {
return 0;
}
// Swap n, m if n > m
if (n > m)
swap(n, m);
// Discover the distinction and examine if
// the distinction is 1, If the
// distinction is 1 return -1 since
// gcd might be 1 for infinite steps
int diff = m - n;
if (diff == 1) {
return -1;
}
// Discover all of the prime components
// of the distinction
vector<int> prime_factors = factorize(diff);
// Initialize the variable pairs to
// discover the variety of steady pairs
int pairs = INT_MAX;
// Iterate by the prime components
// and examine the pairs that
// are attainable.
for (auto p : prime_factors) {
int to_be_added = p - (n % p);
pairs = min(pairs, to_be_added);
}
// Return the variety of pairs
return pairs;
}
// Driver Code
int principal()
{
int n = 1;
int m = 4;
// Perform name
cout << find_maxpairs(n, m) << endl;
return 0;
}
Time Complexity: O(NlogN ) the place N is the scale of the sieve.
Auxiliary House: O(N)
