一个数的所有除数的除数之和

Question

以下方法的很好解释是here。由于格式问题，我无法写在这里。

// 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.can 谁能帮助我了解这背后的直觉循环。

我从 here

那里得到了这个

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; 
}

Answer 1

首先考虑这个语句：

(p₁⁰ + p₁¹ +…+ p₁^k₁) * (p₂⁰ + p₂¹ +…+ p₂^k₂)

现在，任何p^a的约数，对于p为质数，是p⁰，p¹，……，p^a，除数之和为：

((p₁⁰) + (p₁⁰ + p₁¹) + .... + (p₁ ⁰ + p₁¹ + ...+ p_k¹)) * ((p₂⁰) + (p₂⁰ + p₂¹) + (p₂⁰ + p₂¹ + p₂²) + ... (p₂⁰ + p₂¹ + p₂² + .. + p₂^k₂))

你可以认为上面的语句等同于下面的语句：

[[p₁⁰ * (k₁ + 1) + p₁¹ * k₁ + p₁² * (k₁ - 1 ) + .... + (p₁^{k ₁} * 1) ]] * [p₂⁰ * (k ₂ + 1) + p₂¹ * (k₂) + p₂² * (k₂ - 1 ) + .... + (p₂^k₂ * 1) ]] 在您在 post 中编写的代码中，执行了最后一条语句。

例如，如果您考虑 n = 54 = 3³ * 2¹,
ans 以这种格式计算：

ans = (2⁰ * 2 + 2¹ * 1) * (3⁰ * 4 + 3¹ * 3 + 3² * 2 + 3³ *1) = 4 * 58 = 232

一个数的所有除数的除数之和

sum of divisors of all divisors of a number

c++

algorithm

discrete-mathematics

number-theory