python

6.9 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 97. 约数之和

一、题目描述

假设现在有两个自然数 A 和 B，S 是 A^B 的所有约数之和。

请你求出 S~ mod ~9901 的值是多少。

输入格式 在一行中输入用空格隔开的两个整数 A 和 B。

输出格式 输出一个整数，代表 S~ mod~ 9901 的值。

数据范围 0≤A,B≤5×10^7

输入样例：

2 3

输出样例：

注意: A 和 B 不会同时为 0。

二、理论知识

唯一分解

\large N=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}

约数个数

\large (\alpha_1+1)(\alpha_2+1)...(\alpha_k+1)

证明:因为\large p_1^{\alpha_1}的约数有\large p_1^0,p_1^1,p_1^2,...,p_1^{\alpha_1}，共\large a_1+1个,同理p_k^{\alpha_k}的约数有\large a_k+1个,根据乘法原理，就知道了约数的总个数。

约数和

\large (1+p_1^1+p_1^2+...+p_1^{\alpha_1})(1+p_2^1+p_2^2+...+p_2^{\alpha_2})...(1+p_n^1+p_n^2+...+p_n^{\alpha_n})

证明：p_1^{a_1} 的约数有p_1^{0},p_1^{1},p_1^{2}...p_1^{a_1}共 a_1+1个，p_2^{a_2}...p_k^{a_k} 同理，n的一个约数就是在p_1^{a_1},p_2^{a_2},p_3^{a_3}...p_k^{a_k} 每一个的约数中任挑一个组成的，挑法的个数就是约数个数，根据乘法原理他们的和为(p_1^0+p_1^1+...+p_1^{a_1})(p_2^0+p_2^1+...+p_2^{a_2})...(p_k^0+p_k^1+...+p_k^{a_k})

练习题

约数之和

分解质因数

举栗子: `180=2^2∗3^2∗5^1`

约数个数：(2+1)(2+1)(1+1)=18

约数和：(1+2+4)(1+3+9)(1+5)=546

三、分治法求解等比数列求和

巧妙的数学变换

令\large sum(p, k)=p^0+p^1+…+p^{k−1}

k为偶数

\large sum(p,k)=p^0+p^1+…+p^{k/2−1}+p^{k/2}+p^{k/2+1}+…+p^{k−1} \\
\Rightarrow  \\
(p^0+p^1+…+p^{k/2−1})+p^{k/2}∗(p^0+p^1+…+p^{k/2−1}) \\
\Rightarrow  \\
sum(p,k/2)+p^{k/2}∗sum(p,k/2) \\ 
\Rightarrow  \\
(p^{k/2}+1)∗sum(p,k/2)

解释：这样我们就得到了一个递推式，

p^{k/2} 可以用快速幂计算

sum(p,k/2) 由于我们的递推是从小到大推的，在推sum(p,k)时，sum(p,k/2)已经算完了，可以直接用。

k为奇数 为了更方便调用我们写的偶数项情况，可以单独拿出最后一项，把剩下的项转化为求偶数项的情况来考虑，再加上最后一项，就是奇数项的情况了。也即

\large sum(p,k)=p^0+p^1+p^2+...+p^{k-1} \\
= sum(p,k-1)+p^{k-1} $$

当然，也可以拿出来第一项，就是
$$\large sum(p,k)=p^0+p^1+p^2+...+p^{k-1} \\
  = p^0+p\times (p^0+p^1+...+p^{k-2}) \\
  = 1+ p \times sum(p,k-1)

下面的代码实现中，我将使用拿出最后一项的办法：

int sum(int p, int k) {
    if(k == 1) return 1;  //边界
    if(k % 2 == 0)  
        return (LL)(qmi(p, k / 2) + 1) * sum(p, k / 2) % mod;
    return (qmi(p, k - 1) + sum(p, k - 1)) % mod;
}

实现代码

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

const int mod = 9901;
int A, B;

// 分解质因数
unordered_map<int, int> primes; // map存的是数对，key+value,默认按key由小到大排序
void divide(int x) {
    for (int i = 2; i * i <= x; i++)
        while (x % i == 0) primes[i]++, x /= i;
    if (x > 1) primes[x]++;
}

// 快速幂
int qmi(int a, int b) {
    int res = 1;
    while (b) { // 对b进行二进制分解（我给起的名），枚举b的每一个二进制位
        if (b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

// 分治法求等比数列求和公式
int sum(int p, int k) {
    if (k == 1) return 1; // 递归出口
    if (k % 2 == 0)       // 偶数
        return (LL)(qmi(p, k / 2) + 1) * sum(p, k / 2) % mod;
    return (qmi(p, k - 1) + sum(p, k - 1)) % mod; // 奇数
}

int main() {
    cin >> A >> B;
    // 对A分解质因子
    divide(A);

    int res = 1;
    for (auto it : primes) {
        // p是质因子，k是质因子的次数
        int p = it.first, k = it.second * B; // 约数和公式，需要到每个质因子的it.second次方*B

        // res要乘上每一项, 注意这里是k + 1
        res = (LL)res * sum(p, k + 1) % mod; // 满满的套路感
    }
    if (!A) res = 0; // 还要特判A是不是0,注意思考数据边界
    cout << res << endl;
    return 0;
}

时间复杂度 O(\sqrt{n}lognlogn)

四、等比数列求和公式

\large p^0+p^1+p^2+...+p^{k-1}=\frac{p^{k}-1}{p-1}

除了分治法外，还可以用 乘等比数列和公式 得出分子，再 乘分母逆元 的做法:

快速幂求逆元 这样的话，就可以愉快地套用高中学的等比数列和公式来求每一项，但这里需要 特判逆元不存在 的情况:

分母p-1是mod的倍数，不存在逆元，这时直接乘(1+p^1+…p^k)\% mod, 即 k+1
分母p-1不是mod的倍数，存在逆元，这是需要用 快速幂求分子，再用 快速幂求分母的逆元，两者相乘就得到了每一项

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

const int mod = 9901;
int A, B;

//分解质因数
map<int, int> primes; // map存的是数对，key+value,默认按key由小到大排序
void divide(int x) {
    for (int i = 2; i <= x / i; i++)
        while (x % i == 0) primes[i]++, x /= i;
    if (x > 1) primes[x]++;
}

//快速幂
int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%d %d", &A, &B);
    //对A分解质因子
    divide(A);

    int res = 1;
    for (auto it : primes) {
        // p是质因子，k是质因子的次数
        int p = it.first, k = it.second * B;
        // res要乘上每一项, 注意这里是k + 1
        if ((p - 1) % mod == 0) {
            //不存在逆元，由于p-1的是mod的倍数, 故p%mod=1
            //所以1 + p + ... + p^k每个数%mod都是1，共k + 1个数，总就是k + 1
            res = (LL)res * (k + 1) % mod;
        } else
            //分子用快速幂计算，注意标准公式和此题的区别，k+1
            //分母用费马小定理求逆元 qmi(p-1,mod-2)
            res = (LL)res * (qmi(p, k + 1) - 1) % mod * qmi(p - 1, mod - 2) % mod;
    }
    if (!A) res = 0;
    printf("%d\n", (res % mod + mod) % mod);
    return 0;
}

时间复杂度O(\sqrt{n}logn)

6.9 KiB Raw Permalink Blame History Unescape Escape