约数和问题

问题链接：https://ac.nowcoder.com/acm/contest/998/F

题意：求a^b的所有约数的和。

知识点：数学（质因数分解、唯一分解定理、约数和公式）、分治递归。

相关介绍：

唯一分解定理：每个大于1的自然数n均可分解为有限个素数之积，如不计素数在乘积中的顺序，那么这种分解方式是唯一的。并且n可以唯一写成p1^a1p2^a2p3^a3……p_n^a_n
质因数分解：我们可以保证当n被升序的每一个数除到不能除时，其因数都是质数，具体证明见线性筛。
约数个数公式：由①中记法，我们记N为约数的个数，以p₁^a₁为例，其p₁⁰……p₁^a₁都是n的约数，于是就有a₁+1个，同时根据乘法原理，则N = （a₁ + 1)(a₂ + 1)(a₃ + 1)……（a_n + 1)
约数和公式：由③，我们相当于是做个一个排列，而对于每种情况，都是只取其中一种，不难发现，记S为所有约数之和，则S = （p₁⁰ + p₁¹ + …… + p₁^a₁）……（p_n⁰ + p_n¹ + …… + p_n^a_n）
由于是求的a^b的约数之和，我们不妨先将a记作①中形式，那么对于①中的每个p，其指数都为a1*b。

思路：

相关知识点都已经给出，我们的思路也不难得到，那就是通过分解a的质因数，然后求所有的质因数（注意加了b次方）之和。
注意在求解约数和时，我们采取的是一种递归的方法，因为我们可以做以下推导，得到递归思路，进而避免了不必要的计算。
S(p,k) = p⁰ + p¹ + …… + p^k，其中p代表质因数，k代表其最高次方
当k为奇数时，S（p,k） = p⁰ + p¹ + …… + p^k = p⁰ + p¹ + …… + p^{k/2 - 1} + p^k/2 + …… + p^k = p⁰ + p¹ + …… + p^{k/2 - 1} + p^k/2(^{p⁰ + p¹ + …… + p^{k/2 - 1}}) + p^k=(1 + p^k/2)S（p, k / 2）+ p^k
当k为偶数时，也一样的推。

总结：

千万要注意运算符的优先级，k & 1 == 1与（k & 1）== 1是不一样的！！！

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = 9901;

int qpow(int a, int b)
{
    int res = 1;
    a %= mod;
    while(b)
    {
        if(b & 1)   res = res % mod * a % mod;
        a = a % mod * a % mod;
        b >>= 1;
    }
    return res % mod;
}
int sum(int p, int k)
{
    if(k == 0)  return 1;
    else if(k % 2 == 0)
        return ((1 + qpow(p, k >> 1)) * sum(p, (k >> 1) - 1) + qpow(p, k)) % mod;
    else
        return ((1 + qpow(p, (k + 1) >> 1)) * sum(p, (k - 1) >> 1)) % mod;
}

int main()
{
    ios::sync_with_stdio(false);
    int a, b;   cin >> a >> b;
    int ans = 1;
    for(int i = 2; i <= a; i++)
    {
        int s = 0;
        while(a % i == 0)
        {
            s++;
            a /= i;
        }
        if(s) ans = ans * sum(i, s * b) % mod;
    }
    if(a == 0)
        cout << 0 << endl;
    else
        cout << ans << endl;
    return 0;
}

约数和问题

原文链接: https://www.cnblogs.com/ACM-Epoch/p/13342227.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368905

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

约数和问题

相关推荐