Количество множителей очень большого числа N по модулю M, где M - любое простое число
Для большого числа N задача состоит в том, чтобы найти общее количество множителей числа N по модулю M, где M - любое простое число.
Примеры:
Input: N = 9699690, M = 17
Output: 1
Explanation:
Total Number of factors of 9699690 is 256 and (256 % 17) = 1
Input: N = 193748576239475639, M = 9
Output: 8
Explanation:
Total Number of factors of 9699690 is 256 and (256 % 17) = 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Определение факторов числа:
В математике множитель целого числа N, также называемый делителем N, представляет собой целое число M, которое можно умножить на некоторое целое число, чтобы получить N.
Любое число можно записать как:
N = (P1A1) * (P2A2) * (P3A3) …. (PnAn)
где P1, P2, P3… Pn - различные простые числа, а A1, A2, A3… An - количество раз, которое встречается соответствующее простое число.
Общая формула общего количества факторов данного числа будет:
Factors = (1+A1) * (1+A2) * (1+A3) * … (1+An)
где A1, A2, A3,… An - количество различных простых делителей N.
Здесь реализация Sieve для нахождения простого факторизации большого числа не может использоваться, потому что для этого требуется пропорциональное пространство.
Подход:
- Подсчитайте, сколько раз 2 - это множитель данного числа N.
- Итерируйте от 3 до √ (N), чтобы найти, сколько раз простое число делит конкретное число, которое каждый раз уменьшается на N / i .
- Разделите число N на соответствующий ему наименьший простой делитель, пока N не станет равным 1 .
- Найдите количество делителей числа по формуле
Factors = (1+A1) * (1+A2) * (1+A3) * … (1+An)
Below is the implementation of the above approach.
C++
// C++ implementation to find the // Number of factors of very // large number N modulo M #include <bits/stdc++.h> using namespace std; #define ll long long ll mod = 1000000007; // Function for modular // multiplication ll mult(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; } // Function to find the number // of factors of large Number N ll calculate_factors(ll n) { ll ans, cnt; cnt = 0; ans = 1; // Count the number of times // 2 divides the number N while (n % 2 == 0) { cnt++; n = n / 2; } // Condition to check // if 2 divides it if (cnt) { ans = mult(ans, (cnt + 1)); } // Check for all the possible // numbers that can divide it for ( int i = 3; i <= sqrt (n); i += 2) { cnt = 0; // Loop to check the number // of times prime number // i divides it while (n % i == 0) { cnt++; n = n / i; } // Condition to check if // prime number i divides it if (cnt) { ans = mult(ans, (cnt + 1)); } } // Condition to check if N // at the end is a prime number. if (n > 2) { ans = mult(ans, (2)); } return ans % mod; } // Driver Code int main() { ll n = 193748576239475639; mod = 17; cout << calculate_factors(n) << endl; return 0; } |
Java
// Java implementation to find the // Number of factors of very // large number N modulo M class GFG{ static long mod = 1000000007L; // Function for modular // multiplication static long mult( long a, long b) { return ((a % mod) * (b % mod)) % mod; } // Function to find the number // of factors of large Number N static long calculate_factors( long n) { long ans, cnt; cnt = 0 ; ans = 1 ; // Count the number of times // 2 divides the number N while (n % 2 == 0 ) { cnt++; n = n / 2 ; } // Condition to check // if 2 divides it if (cnt % 2 == 1 ) { ans = mult(ans, (cnt + 1 )); } // Check for all the possible // numbers that can divide it for ( int i = 3 ; i <= Math.sqrt(n); i += 2 ) { cnt = 0 ; // Loop to check the number // of times prime number // i divides it while (n % i == 0 ) { cnt++; n = n / i; } // Condition to check if // prime number i divides it if (cnt % 2 == 1 ) { ans = mult(ans, (cnt + 1 )); } } // Condition to check if N // at the end is a prime number. if (n > 2 ) { ans = mult(ans, ( 2 )); } return ans % mod; } // Driver Code public static void main(String[] args) { long n = 193748576239475639L; mod = 17 ; System.out.print(calculate_factors(n) + "
" ); } } // This code is contributed by sapnasingh4991 |
Python 3
# Python 3 implementation to find the # Number of factors of very # large number N modulo M from math import sqrt mod = 1000000007 # Function for modular # multiplication def mult(a, b): return ((a % mod) * (b % mod)) % mod # Function to find the number # of factors of large Number N def calculate_factors(n): cnt = 0 ans = 1 # Count the number of times # 2 divides the number N while (n % 2 = = 0 ): cnt + = 1 n = n / / 2 # Condition to check # if 2 divides it if (cnt): ans = mult(ans, (cnt + 1 )) # Check for all the possible # numbers that can divide it for i in range ( 3 , int (sqrt(n)), 2 ): cnt = 0 # Loop to check the number # of times prime number # i divides it while (n % i = = 0 ): cnt + = 1 n = n / / i # Condition to check if # prime number i divides it if (cnt): ans = mult(ans, (cnt + 1 )) # Condition to check if N # at the end is a prime number. if (n > 2 ): ans = mult(ans, 2 ) return ans % mod # Driver Code if __name__ = = "__main__" : n = 19374857 mod = 17 print (calculate_factors(n)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation to find the // Number of factors of very // large number N modulo M using System; class GFG{ static long mod = 1000000007L; // Function for modular // multiplication static long mult( long a, long b) { return ((a % mod) * (b % mod)) % mod; } // Function to find the number // of factors of large Number N static long calculate_factors( long n) { long ans, cnt; cnt = 0; ans = 1; // Count the number of times // 2 divides the number N while (n % 2 == 0) { cnt++; n = n / 2; } // Condition to check // if 2 divides it if (cnt % 2 == 1) { ans = mult(ans, (cnt + 1)); } // Check for all the possible // numbers that can divide it for ( int i = 3; i <= Math.Sqrt(n); i += 2) { cnt = 0; // Loop to check the number // of times prime number // i divides it while (n % i == 0) { cnt++; n = n / i; } // Condition to check if // prime number i divides it if (cnt % 2 == 1) { ans = mult(ans, (cnt + 1)); } } // Condition to check if N // at the end is a prime number. if (n > 2) { ans = mult(ans, (2)); } return ans % mod; } // Driver Code public static void Main(String[] args) { long n = 193748576239475639L; mod = 17; Console.Write(calculate_factors(n) + "
" ); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // javascript implementation to find the // Number of factors of very // large number N modulo M mod = 1000000007; // Function for modular // multiplication function mult( a , b) { return ((a % mod) * (b % mod)) % mod; } // Function to find the number // of factors of large Number N function calculate_factors( n) { var ans, cnt; cnt = 0; ans = 1; // Count the number of times // 2 divides the number N while (n % 2 == 0) { cnt++; n = n / 2; } // Condition to check // if 2 divides it if (cnt % 2 == 1) { ans = mult(ans, (cnt + 1)); } // Check for all the possible // numbers that can divide it for (i = 3; i <= Math.sqrt(n); i += 2) { cnt = 0; // Loop to check the number // of times prime number // i divides it while (n % i == 0) { cnt++; n = n / i; } // Condition to check if // prime number i divides it if (cnt % 2 == 1) { ans = mult(ans, (cnt + 1)); } } // Condition to check if N // at the end is a prime number. if (n > 2) { ans = mult(ans, (2)); } return ans % mod; } // Driver Code var n = 193748576239475639; mod = 17; document.write(calculate_factors(n)); // This code contributed by shikhasingrajput </script> |
8
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.