сумма делителей всех делителей числа - PullRequest
Новая
       70

сумма делителей всех делителей числа

0 голосов
/ 11 февраля 2019

Очень хорошее объяснение нижеследующего подхода: здесь . Я не смог написать здесь из-за проблем с форматированием.

// C ++ программа для поиска суммы делителей всех делителейнатурального числа.

#include<bits/stdc++.h> 
using namespace std; 

// Returns sum of divisors of all the divisors 
// of n 
int sumDivisorsOfDivisors(int n) 
{ 
    // Calculating powers of prime factors and 
    // storing them in a map mp[]. 
    map<int, int> mp; 
    for (int j=2; j<=sqrt(n); j++) 
    { 
        int count = 0; 
        while (n%j == 0) 
        { 
            n /= j; 
            count++; 
        } 

        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. 
    int ans = 1; 
    for (auto it : mp) 
    { 
        int pw = 1; 
        int sum = 0; 

        for (int i=it.second+1; i>=1; i--) 
        { 
            sum += (i*pw); 
            pw *= it.first; 
        } 
        ans *= sum; 
    } 

    return ans; 
} 

// Driven Program 
int main() 
{ 
    int n = 10; 
    cout << sumDivisorsOfDivisors(n); 
    return 0; 
}

Я не понимаю, что происходит в этом цикле, вместо того, чтобы добавить к ANS, что они умножают сумму, как они рассчитывают (p^(a+1)-1)/(p-1), и это к ANS. Кто-нибудь может мне помочь с интуицией, стоящей за этимцикл.

Я получил это от здесь 

for (auto it : mp) 
{ 
    int pw = 1; 
    int sum = 0; 

    for (int i=it.second+1; i>=1; i--) 
    { 
        sum += (i*pw); 
        pw *= it.first; 
    } 
    ans *= sum; 
}

1 Ответ

0 голосов
/ 11 февраля 2019

Сначала рассмотрим это утверждение:

(p 1 0 + p 1 1 +… + p 1 k 1 ) * (p 2 0 + p 2 1 +… + p 2 k 2 )

Теперь делители любого p a , для p в качестве простых чисел, p 0 , p 1 , ……, p a , а сумма делителей будет:

((p 1 0 ) + (p 1 0 + p 1 1 ) + .... + (p 1 0 + p 1 1 + ... + p k 1 )) * ((p 2 0 ) + (p 2 0 +p 2 1 ) + (p 2 0 + p 2 1 +p 2 2 ) + ... (p 2 0 + p 2 1 + p 2 2 + .. + p 2 k 2 ))

Вы можете рассмотреть вопросve оператор, эквивалентный нижнему оператору:

[[p 1 0 * (k 1 + 1) + p 1 1 * k 1 + p 1 2 * (k 1 - 1) + .... + (p 1 k 1 * 1)]] * [[p 2 0 *(k 2 + 1) + p 2 1 * (k 2 ) + p 2 2 * (k 2 - 1) + .... + (p 2 k 2 * 1)]] в коде, который вы пишете в посте, было выполнено последнее утверждение.

, например, если учесть n = 54 = 3 3 * 2 1 ,
ANS рассчитывается в следующем формате:

ANS = (2 0 * 2 + 2 1 * 1) * (3 0 * 4 + 3 1 * 3 + 3 2 * 2 + 3 3 * 1) = 4 * 58 = 232

...