#practiceLinkDiv { 표시: 없음 !중요; }자연수가 주어지면 N 작업은 n의 모든 약수 중 약수의 합을 구하는 것입니다.
예:
Input : n = 54 Output : 232 Divisors of 54 = 1 2 3 6 9 18 27 54. Sum of divisors of 1 2 3 6 9 18 27 54 are 1 3 4 12 13 39 40 120 respectively. Sum of divisors of all the divisors of 54 = 1 + 3 + 4 + 12 + 13 + 39 + 40 + 120 = 232. Input : n = 10 Output : 28 Divisors of 10 are 1 2 5 10 Sums of divisors of divisors are 1 3 6 18. Overall sum = 1 + 3 + 6 + 18 = 28Recommended Practice 제수의 합 찾기 시도해 보세요!
임의의 숫자라는 사실을 이용하여 N 소인수의 곱으로 표현될 수 있다 N =피1k1xp2k2x ... 여기서 p1피2...은 소수입니다.
n의 모든 약수는 p로 표현될 수 있습니다.1에이xp2비x ... 여기서 0<= a <= k1 and 0 <= b <= k2.
이제 제수의 합은 p의 모든 거듭제곱의 합이 됩니다.1- 피1피11....피1k1p의 모든 거듭제곱을 곱한 값2- 피2피21....피2k1
n의 제수의 합
= (피1xp2) + (p11xp2) +.....+ (p1k1xp2) +....+ (p1xp21) + (p11xp21) +.....+ (p1k1xp21) +........+
(피1xp2k2) + (p11xp2k2) +......+ (p1k1xp2k2).
= (피1+ 피11+...+ 피1k1) x p2+ (p1+ 피11+...+ 피1k1) x p21+......+ (p1+ 피11+...+ 피1k1) x p2k2.
= (피1+ 피11+...+ 피1k1) x (p2+ 피21+...+ 피2k2).
이제 모든 p의 제수는에이p의 경우 소수는 p이므로피1......p에이. 그리고 제수의 합은 (p(a+1)- 1)/(p -1) f(p)로 정의하겠습니다.
따라서 모든 제수의 제수의 합은 다음과 같습니다.
= (에프(피1) + f(피11) +...+ 에프(피1k1)) x (f(p2) + f(피21) +...+ 에프(피2k2)).
따라서 소인수분해를 통해 숫자 n이 주어지면 모든 약수의 약수의 합을 찾을 수 있습니다. 하지만 이 문제에서는 n이 배열 요소의 곱이라는 것을 알 수 있습니다. 따라서 각 요소의 소인수분해를 구하고 다음 사실을 사용하여비xa기음=ab+c.
다음은 이 접근 방식의 구현입니다.
C++// C++ program to find sum of divisors of all // the divisors of a natural number. #include
// Java program to find sum of divisors of all // the divisors of a natural number. import java.util.HashMap; class GFG { // Returns sum of divisors of all the divisors // of n public static int sumDivisorsOfDivisors(int n) { // Calculating powers of prime factors and // storing them in a map mp[]. HashMap<Integer Integer> mp = new HashMap<>(); for (int j = 2; j <= Math.sqrt(n); j++) { int count = 0; while (n % j == 0) { n /= j; count++; } if (count != 0) mp.put(j count); } // If n is a prime number if (n != 1) mp.put(n 1); // For each prime factor calculating (p^(a+1)-1)/(p-1) // and adding it to answer. int ans = 1; for (HashMap.Entry<Integer Integer> entry : mp.entrySet()) { int pw = 1; int sum = 0; for (int i = entry.getValue() + 1; i >= 1; i--) { sum += (i * pw); pw *= entry.getKey(); } ans *= sum; } return ans; } // Driver code public static void main(String[] args) { int n = 10; System.out.println(sumDivisorsOfDivisors(n)); } } // This code is contributed by // sanjeev2552
# Python3 program to find sum of divisors # of all the divisors of a natural number. import math as mt # Returns sum of divisors of all # the divisors of n def sumDivisorsOfDivisors(n): # Calculating powers of prime factors # and storing them in a map mp[]. mp = dict() for j in range(2 mt.ceil(mt.sqrt(n))): count = 0 while (n % j == 0): n //= j count += 1 if (count): mp[j] = count # If n is a prime number if (n != 1): mp[n] = 1 # For each prime factor calculating # (p^(a+1)-1)/(p-1) and adding it to answer. ans = 1 for it in mp: pw = 1 summ = 0 for i in range(mp[it] + 1 0 -1): summ += (i * pw) pw *= it ans *= summ return ans # Driver Code n = 10 print(sumDivisorsOfDivisors(n)) # This code is contributed # by mohit kumar 29
// C# program to find sum of divisors of all // the divisors of a natural number. using System; using System.Collections.Generic; class GFG { // Returns sum of divisors of // all the divisors of n public static int sumDivisorsOfDivisors(int n) { // Calculating powers of prime factors and // storing them in a map mp[]. Dictionary<int int> mp = new Dictionary<int int>(); for (int j = 2; j <= Math.Sqrt(n); j++) { int count = 0; while (n % j == 0) { n /= j; count++; } if (count != 0) mp.Add(j count); } // If n is a prime number if (n != 1) mp.Add(n 1); // For each prime factor // calculating (p^(a+1)-1)/(p-1) // and adding it to answer. int ans = 1; foreach(KeyValuePair<int int> entry in mp) { int pw = 1; int sum = 0; for (int i = entry.Value + 1; i >= 1; i--) { sum += (i * pw); pw = entry.Key; } ans *= sum; } return ans; } // Driver code public static void Main(String[] args) { int n = 10; Console.WriteLine(sumDivisorsOfDivisors(n)); } } // This code is contributed // by Princi Singh
<script> // Javascript program to find sum of divisors of all // the divisors of a natural number. // Returns sum of divisors of all the divisors // of n function sumDivisorsOfDivisors(n) { // Calculating powers of prime factors and // storing them in a map mp[]. let mp = new Map(); for (let j = 2; j <= Math.sqrt(n); j++) { let count = 0; while (n % j == 0) { n = Math.floor(n/j); count++; } if (count != 0) mp.set(j count); } // If n is a prime number if (n != 1) mp.set(n 1); // For each prime factor calculating (p^(a+1)-1)/(p-1) // and adding it to answer. let ans = 1; for (let [key value] of mp.entries()) { let pw = 1; let sum = 0; for (let i = value + 1; i >= 1; i--) { sum += (i * pw); pw = key; } ans *= sum; } return ans; } // Driver code let n = 10; document.write(sumDivisorsOfDivisors(n)); // This code is contributed by patel2127 </script>
산출:
28
시간 복잡도: O(?n 로그 n)
보조 공간: 에)
최적화:
사용할 수 있는 값을 찾아야 하는 입력이 여러 개인 경우 에라토스테네스의 체 에서 논의한 바와 같이 이것 우편.