Givet Q-frågor av typen: L R för varje fråga måste du skriva ut det maximala antalet divisorer som ett nummer x (L<= x <= R) har.
Exempel:
L = 1 R = 10 : 1 has 1 divisor. 2 has 2 divisors. 3 has 2 divisors. 4 has 3 divisors. 5 has 2 divisors. 6 has 4 divisors. 7 has 2 divisors. 8 has 4 divisors. 9 has 3 divisors. 10 has 4 divisors. So the answer for above query is 4 as it is the maximum number of divisors a number has in [1 10].
Förutsättningar: Eratosthenes sikt Segmentträd
Nedan finns steg för att lösa problemet.
- Låt oss först se hur många antal divisorer som gör ett tal n = p1k1* sid2k2* ... * sidnkn (där sid1sid2... sidnär primtal) har; svaret är (k1+ 1)*(k2+ 1)*...*(kn+ 1) . Hur? För varje primtal i primtalsfaktoriseringen kan vi ha sitt ki+ 1 möjliga potenser i en divisor (0 1 2... ki).
- Låt oss nu se hur vi kan hitta primtalsfaktoriseringen av ett tal som vi först bygger en array minsta_prime[] som lagrar den minsta primtalsdelaren av i på ith index vi dividerar ett tal med dess minsta primtalsdelare för att få ett nytt tal (vi har också den minsta primtalsvisaren av detta nya tal lagrad) vi fortsätter att göra det tills det minsta primtaltalet av talet ändras när den minsta primtalsfaktorn för det nya talet skiljer sig från det tidigare talets vi har kiför ithprimtal i primtalsfaktoriseringen av det givna talet.
- Slutligen får vi antalet divisorer för alla siffror och lagrar dessa i ett segmentträd som upprätthåller de maximala talen i segmenten. Vi svarar på varje fråga genom att fråga segmentträdet.
// A C++ implementation of the above idea to process // queries of finding a number with maximum divisors. #include
// Java implementation of the above idea to process // queries of finding a number with maximum divisors. import java.util.*; class GFG { static int maxn = 10005; static int INF = 999999; static int []smallest_prime = new int[maxn]; static int []divisors = new int[maxn]; static int []segmentTree = new int[4 * maxn]; // Finds smallest prime factor of all numbers // in range[1 maxn) and stores them in // smallest_prime[] smallest_prime[i] should // contain the smallest prime that divides i static void findSmallestPrimeFactors() { // Initialize the smallest_prime factors // of all to infinity for (int i = 0 ; i < maxn ; i ++ ) smallest_prime[i] = INF; // to be built like eratosthenes sieve for (int i = 2; i < maxn; i++) { if (smallest_prime[i] == INF) { // prime number will have its // smallest_prime equal to itself smallest_prime[i] = i; for (int j = i * i; j < maxn; j += i) // if 'i' is the first // prime number reaching 'j' if (smallest_prime[j] > i) smallest_prime[j] = i; } } } // number of divisors of n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // are equal to (k1+1) * (k2+1) ... (kn+1) // this function finds the number of divisors of all numbers // in range [1 maxn) and stores it in divisors[] // divisors[i] stores the number of divisors i has static void buildDivisorsArray() { for (int i = 1; i < maxn; i++) { divisors[i] = 1; int n = i p = smallest_prime[i] k = 0; // we can obtain the prime factorization of // the number n n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // using the smallest_prime[] array we keep dividing n // by its smallest_prime until it becomes 1 // whilst we check if we have need to set k zero while (n > 1) { n = n / p; k ++; if (smallest_prime[n] != p) { // use p^k initialize k to 0 divisors[i] = divisors[i] * (k + 1); k = 0; } p = smallest_prime[n]; } } } // builds segment tree for divisors[] array static void buildSegtmentTree(int node int a int b) { // leaf node if (a == b) { segmentTree[node] = divisors[a]; return ; } //build left and right subtree buildSegtmentTree(2 * node a (a + b) / 2); buildSegtmentTree(2 * node + 1 ((a + b) / 2) + 1 b); //combine the information from left //and right subtree at current node segmentTree[node] = Math.max(segmentTree[2 * node] segmentTree[2 *node + 1]); } // returns the maximum number of divisors in [l r] static int query(int node int a int b int l int r) { // If current node's range is disjoint // with query range if (l > b || a > r) return -1; // If the current node stores information // for the range that is completely inside // the query range if (a >= l && b <= r) return segmentTree[node]; // Returns maximum number of divisors from left // or right subtree return Math.max(query(2 * node a (a + b) / 2 l r) query(2 * node + 1 ((a + b) / 2) + 1 b l r)); } // Driver Code public static void main(String[] args) { // First find smallest prime divisors // for all the numbers findSmallestPrimeFactors(); // Then build the divisors[] array to store // the number of divisors buildDivisorsArray(); // Build segment tree for the divisors[] array buildSegtmentTree(1 1 maxn - 1); System.out.println('Maximum divisors that a number ' + 'has in [1 100] are ' + query(1 1 maxn - 1 1 100)); System.out.println('Maximum divisors that a number ' + 'has in [10 48] are ' + query(1 1 maxn - 1 10 48)); System.out.println('Maximum divisors that a number ' + 'has in [1 10] are ' + query(1 1 maxn - 1 1 10)); } } // This code is contributed by PrinciRaj1992
# Python 3 implementation of the above # idea to process queries of finding a # number with maximum divisors. maxn = 1000005 INF = 99999999 smallest_prime = [0] * maxn divisors = [0] * maxn segmentTree = [0] * (4 * maxn) # Finds smallest prime factor of all # numbers in range[1 maxn) and stores # them in smallest_prime[] smallest_prime[i] # should contain the smallest prime that divides i def findSmallestPrimeFactors(): # Initialize the smallest_prime # factors of all to infinity for i in range(maxn ): smallest_prime[i] = INF # to be built like eratosthenes sieve for i in range(2 maxn): if (smallest_prime[i] == INF): # prime number will have its # smallest_prime equal to itself smallest_prime[i] = i for j in range(i * i maxn i): # if 'i' is the first prime # number reaching 'j' if (smallest_prime[j] > i): smallest_prime[j] = i # number of divisors of n = (p1 ^ k1) * # (p2 ^ k2) ... (pn ^ kn) are equal to # (k1+1) * (k2+1) ... (kn+1). This function # finds the number of divisors of all numbers # in range [1 maxn) and stores it in divisors[] # divisors[i] stores the number of divisors i has def buildDivisorsArray(): for i in range(1 maxn): divisors[i] = 1 n = i p = smallest_prime[i] k = 0 # we can obtain the prime factorization # of the number n n = (p1 ^ k1) * (p2 ^ k2) # ... (pn ^ kn) using the smallest_prime[] # array we keep dividing n by its # smallest_prime until it becomes 1 whilst # we check if we have need to set k zero while (n > 1): n = n // p k += 1 if (smallest_prime[n] != p): # use p^k initialize k to 0 divisors[i] = divisors[i] * (k + 1) k = 0 p = smallest_prime[n] # builds segment tree for divisors[] array def buildSegtmentTree( node a b): # leaf node if (a == b): segmentTree[node] = divisors[a] return #build left and right subtree buildSegtmentTree(2 * node a (a + b) // 2) buildSegtmentTree(2 * node + 1 ((a + b) // 2) + 1 b) #combine the information from left #and right subtree at current node segmentTree[node] = max(segmentTree[2 * node] segmentTree[2 * node + 1]) # returns the maximum number of # divisors in [l r] def query(node a b l r): # If current node's range is disjoint # with query range if (l > b or a > r): return -1 # If the current node stores information # for the range that is completely inside # the query range if (a >= l and b <= r): return segmentTree[node] # Returns maximum number of divisors # from left or right subtree return max(query(2 * node a (a + b) // 2 l r) query(2 * node + 1 ((a + b) // 2) + 1 b l r)) # Driver code if __name__ == '__main__': # First find smallest prime divisors # for all the numbers findSmallestPrimeFactors() # Then build the divisors[] array to # store the number of divisors buildDivisorsArray() # Build segment tree for the divisors[] array buildSegtmentTree(1 1 maxn - 1) print('Maximum divisors that a number has ' ' in [1 100] are ' query(1 1 maxn - 1 1 100)) print('Maximum divisors that a number has' ' in [10 48] are ' query(1 1 maxn - 1 10 48)) print( 'Maximum divisors that a number has' ' in [1 10] are ' query(1 1 maxn - 1 1 10)) # This code is contributed by ita_c
// C# implementation of the above idea // to process queries of finding a number // with maximum divisors. using System; class GFG { static int maxn = 10005; static int INF = 999999; static int []smallest_prime = new int[maxn]; static int []divisors = new int[maxn]; static int []segmentTree = new int[4 * maxn]; // Finds smallest prime factor of all numbers // in range[1 maxn) and stores them in // smallest_prime[] smallest_prime[i] should // contain the smallest prime that divides i static void findSmallestPrimeFactors() { // Initialize the smallest_prime // factors of all to infinity for (int i = 0 ; i < maxn ; i ++ ) smallest_prime[i] = INF; // to be built like eratosthenes sieve for (int i = 2; i < maxn; i++) { if (smallest_prime[i] == INF) { // prime number will have its // smallest_prime equal to itself smallest_prime[i] = i; for (int j = i * i; j < maxn; j += i) // if 'i' is the first // prime number reaching 'j' if (smallest_prime[j] > i) smallest_prime[j] = i; } } } // number of divisors of // n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // are equal to (k1+1) * (k2+1) ... (kn+1) // this function finds the number of divisors // of all numbers in range [1 maxn) and stores // it in divisors[] divisors[i] stores the // number of divisors i has static void buildDivisorsArray() { for (int i = 1; i < maxn; i++) { divisors[i] = 1; int n = i p = smallest_prime[i] k = 0; // we can obtain the prime factorization of // the number n // n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // using the smallest_prime[] array // we keep dividing n by its smallest_prime // until it becomes 1 whilst we check if // we have need to set k zero while (n > 1) { n = n / p; k ++; if (smallest_prime[n] != p) { // use p^k initialize k to 0 divisors[i] = divisors[i] * (k + 1); k = 0; } p = smallest_prime[n]; } } } // builds segment tree for divisors[] array static void buildSegtmentTree(int node int a int b) { // leaf node if (a == b) { segmentTree[node] = divisors[a]; return; } //build left and right subtree buildSegtmentTree(2 * node a (a + b) / 2); buildSegtmentTree(2 * node + 1 ((a + b) / 2) + 1 b); //combine the information from left //and right subtree at current node segmentTree[node] = Math.Max(segmentTree[2 * node] segmentTree[2 *node + 1]); } // returns the maximum number of divisors in [l r] static int query(int node int a int b int l int r) { // If current node's range is disjoint // with query range if (l > b || a > r) return -1; // If the current node stores information // for the range that is completely inside // the query range if (a >= l && b <= r) return segmentTree[node]; // Returns maximum number of divisors from left // or right subtree return Math.Max(query(2 * node a (a + b) / 2 l r) query(2 * node + 1 ((a + b) / 2) + 1 b l r)); } // Driver Code public static void Main(String[] args) { // First find smallest prime divisors // for all the numbers findSmallestPrimeFactors(); // Then build the divisors[] array // to store the number of divisors buildDivisorsArray(); // Build segment tree for the divisors[] array buildSegtmentTree(1 1 maxn - 1); Console.WriteLine('Maximum divisors that a number ' + 'has in [1 100] are ' + query(1 1 maxn - 1 1 100)); Console.WriteLine('Maximum divisors that a number ' + 'has in [10 48] are ' + query(1 1 maxn - 1 10 48)); Console.WriteLine('Maximum divisors that a number ' + 'has in [1 10] are ' + query(1 1 maxn - 1 1 10)); } } // This code is contributed by 29AjayKumar
<script> // JavaScript implementation of the above idea to process // queries of finding a number with maximum divisors. let maxn = 10005; let INF = 999999; let smallest_prime = new Array(maxn); for(let i=0;i<maxn;i++) { smallest_prime[i]=0; } let divisors = new Array(maxn); for(let i=0;i<maxn;i++) { divisors[i]=0; } let segmentTree = new Array(4 * maxn); for(let i=0;i<4*maxn;i++) { segmentTree[i]=0; } // Finds smallest prime factor of all numbers // in range[1 maxn) and stores them in // smallest_prime[] smallest_prime[i] should // contain the smallest prime that divides i function findSmallestPrimeFactors() { // Initialize the smallest_prime factors // of all to infinity for (let i = 0 ; i < maxn ; i ++ ) smallest_prime[i] = INF; // to be built like eratosthenes sieve for (let i = 2; i < maxn; i++) { if (smallest_prime[i] == INF) { // prime number will have its // smallest_prime equal to itself smallest_prime[i] = i; for (let j = i * i; j < maxn; j += i) { // if 'i' is the first // prime number reaching 'j' if (smallest_prime[j] > i) smallest_prime[j] = i; } } } } // number of divisors of n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // are equal to (k1+1) * (k2+1) ... (kn+1) // this function finds the number of divisors of all numbers // in range [1 maxn) and stores it in divisors[] // divisors[i] stores the number of divisors i has function buildDivisorsArray() { for (let i = 1; i < maxn; i++) { divisors[i] = 1; let n = i; let p = smallest_prime[i] let k = 0; // we can obtain the prime factorization of // the number n n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) // using the smallest_prime[] array we keep dividing n // by its smallest_prime until it becomes 1 // whilst we check if we have need to set k zero while (n > 1) { n = Math.floor(n / p); k++; if (smallest_prime[n] != p) { // use p^k initialize k to 0 divisors[i] = divisors[i] * (k + 1); k = 0; } p = smallest_prime[n]; } } } // builds segment tree for divisors[] array function buildSegtmentTree(nodeab) { // leaf node if (a == b) { segmentTree[node] = divisors[a]; return ; } //build left and right subtree buildSegtmentTree(2 * node a Math.floor((a + b) / 2)); buildSegtmentTree((2 * node) + 1 Math.floor((a + b) / 2) + 1 b); //combine the information from left //and right subtree at current node segmentTree[node] = Math.max(segmentTree[2 * node] segmentTree[(2 *node) + 1]); } // returns the maximum number of divisors in [l r] function query(nodeablr) { // If current node's range is disjoint // with query range if (l > b || a > r) return -1; // If the current node stores information // for the range that is completely inside // the query range if (a >= l && b <= r) return segmentTree[node]; // Returns maximum number of divisors from left // or right subtree return Math.max(query(2 * node a Math.floor((a + b) / 2) l r) query(2 * node + 1 Math.floor((a + b) / 2) + 1 b l r)); } // Driver Code // First find smallest prime divisors // for all the numbers findSmallestPrimeFactors(); // Then build the divisors[] array to store // the number of divisors buildDivisorsArray(); // Build segment tree for the divisors[] array buildSegtmentTree(1 1 maxn - 1); document.write('Maximum divisors that a number ' + 'has in [1 100] are ' + query(1 1 maxn - 1 1 100)+'
'); document.write('Maximum divisors that a number ' + 'has in [10 48] are ' + query(1 1 maxn - 1 10 48)+'
'); document.write('Maximum divisors that a number ' + 'has in [1 10] are ' + query(1 1 maxn - 1 1 10)+'
'); // This code is contributed by avanitrachhadiya2155 </script>
Produktion:
konvertera sträng till datum
Maximum divisors that a number has in [1 100] are 12 Maximum divisors that a number has in [10 48] are 10 Maximum divisors that a number has in [1 10] are 4
Tidskomplexitet: O((maxn + Q) * log(maxn))
- För sil: O(maxn * log(log(maxn)))
- För att beräkna divisorer för varje tal: Okej1 + k2 + ... + kn) < O(log(maxn))
- För att fråga efter varje intervall: O(log(maxn))
Hjälputrymme: På)
Relaterat ämne: