Acwing 97

#include<bits/stdc++.h>

using namespace std;

const int mod=9901;

int qmi(int a,int b)
{
    int ans=1;
    a%=mod;
    
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    
    return ans;
}

int sum(int p,int c)
{
    if(c==1)
        return 1;
    if(c&1)
        return sum(p,c-1)+qmi(p,c-1)%mod;
    return (1+qmi(p,c/2))*sum(p,c/2)%mod;
}

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

分治

首先是数论的公式，约数的和的公式
$$(1+p_1^{}+p_1^2+p_1^3+\cdots +p_1^{c_1})\ast (1+p_2+p_2^2+\cdots +p_2^{c_2})\ast \cdots (1+p_k+\cdots +\cdots +p_k^{c_k})$$

有两种方法求解，第一种方法是快速幂和逆元，因为上面一个括号里面的式子是一个等比数列的求和，需要用到除法，用到除法和取模就需要使用逆元

另一种方法是分治，就是把这个括号里面的元素分成两个部分，和二进制表示有点像，就是相当于去查询之前处理好了的数值，比如说我们知道2 4 8 16 ，给定一个数字 17，我们知道它只比 16 大 1 .很快就可以表示出 17

具体来说就是把括号里面的元素分成两个部分，假设元素的个数是偶数的话

$$\{\begin{array}{l}1+p+p^2+p^3+\cdots +p^{c-1}=sum(p,c)\\ 1+p+p^2+\cdots +p^{c/2-1}前半部分\\ p^{c/2}+\cdots +p^{c-1}后半部分\\ p^{c/2}\ast (1+p+p^2+\cdots +p^{c/2-1})\\ (1+p^{c/2})\ast (1+p+p^2+\cdots +p^{c/2-1}))\\ (1+p^{c/2})\ast sum(p,c/2)\end{array}$$
奇数的时候就直接把最后一项单独拿出来，除了最后一项，剩下的元素的个数是偶数，可以使用前面推出来的偶数的公式

需要注意的一点是，sum 表示的是幂指数到 k-1

自己写的时候幂指数算到 k ，发生了空间限制超出的错误。

算了，就这样吧，那不是主要矛盾，现在自己主要是学习这个分治的思路和记住这个约数和的结论，能够完全理解这个代码并且自己独立地敲出来就可以了

快速幂的模板，需要注意的是输入的 a 本来就比模数大，所以需要先取模一次

试除法分解质因数最后需要检验一下最后一个数字是不是质数，最后一个数字是质数的话，需要更新一下答案，每一次计算都需要取模

假设 a 是 0 ，答案是 0

需要注意还有一个细节，我们是把 a 进行了分解，b 可以直接乘在 a 分解之后的幂指数上面

原文地址：https://blog.csdn.net/L3102250566/article/details/136356077

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！