题解_约数之和

简约

题目

首先需要知道一些基本的数学知识（算数基本定理之类的）

然后推导公式，发现是个等比数列求和，但因为要取模，所以套公式很麻烦。

进行优化，可以用递归来模拟公式，相当于二分计算（奇数的话，留出末项，把前面二分计算，最后乘积）

具体推导过程见图片。

推导过程

代码

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod = 9901;
int n, m, ans = 1;
int qp(int x, int y)
{
    int res = 1;
    x %= mod;
    while(y)
    {
        if(y & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return res % mod;
}
int sum(int p, int k)
{
    if(!k) return 1;
    if(k & 1) return ((1 + qp(p, k / 2 + 1)) * sum(p, k / 2)) % mod;
    return ((p % mod) * sum(p, k - 1) + 1) % mod;
    
}
int main()
{
    ios :: sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 2; i <= n; ++i)
    {
        int tot = 0;
        while(n % i == 0)
        {
            tot++;
            n /= i;
        }
        if(tot) ans = (ans * sum(i, tot * m)) % mod;
    }
    if(!n) puts("0");
    else cout << ans << endl;
    return 0;
}

2020 RP++