Étant donné deux entiers n et M. Trouver le nombre de paires continues possibles avec pgcd(n, m) = 1dans lequel chaque étape 1 peut être incrémenté à la paire.
Exemples:
Saisir: n = 1, m = 4
Sortir: 2
Explication: pgcd(1, 4) =1, à l’étape suivante pgcd(2, 5) =1 donc les paires continues maximales possibles sont 2.Saisir: n = 5, m = 13
Sortir:1
Explication: Seule cette paire est potential avec pgcd(n, m) =1 automotive à l’étape suivante n = 6, m = 14 qui a pgcd = 2 donc la sortie est 1.
Approche: Cela peut être résolu avec l’idée ci-dessous:
Nous devons trouver le okay tel que pgcd(n+okay, m+okay) soit supérieur à 2, il devrait donc y avoir au moins 1 nombre premier qui divise à la fois n+okay et m+okay, à l’exception des cas exceptionnels où n= m et n = m+1. Il devrait y avoir un nombre p qui divise à la fois m+okay et n+okay.
D’où la différence (nm) % p = 0, il suffit donc de regarder les facteurs premiers de nm tels que n+okay % p =0 on prend donc la valeur minimale de p – npercentp qui est le nombre de pas qu’il peut être incrémenté pour que pgcd (n, m) soit 1.
Suivez les étapes mentionnées ci-dessous pour résoudre le problème :
- Construire le tamis pour stocker les plus petits facteurs premiers
- Trouvez le pgcd actuel et si le pgcd preliminary n’est pas égal à 1, retournez 0.
- Echange n, m si n > m
- Trouvez la différence et vérifiez si la différence est de 1, si la différence est de 1, retournez -1 puisque pgcd sera de 1 pour les pas infinis
- Trouvez tous les facteurs premiers de la différence en utilisant la fonction de factorisation.
- Initialiser les paires de variables pour trouver le nombre de paires continues
- Parcourez les facteurs premiers et vérifiez les paires possibles en prenant un minimal de pnpercentp. Renvoie le nombre de paires
Voici la mise en œuvre de l’approche ci-dessus :
C++
// C++ code for the above method
#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;
}
}
}
}
// Operate 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;
}
// Operate to search out the utmost
// potential steady pairs
int find_maxpairs(int n, int m)
{
// Calling the build_sieve
build_sieve();
// Discover the present gcd and if preliminary
// gcd isn't 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 verify if
// the distinction is 1, If the
// distinction is 1 return -1 since
// gcd will probably 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 way of the prime components
// and verify the pairs that
// are potential.
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 predominant()
{
int n = 1;
int m = 4;
// Operate name
cout << find_maxpairs(n, m) << endl;
return 0;
}
Complexité temporelle : O(NlogN ) où N est la taille du tamis.
Espace Auxiliaire : SUR)
