【洛谷】P1593 因子和

洛谷P1593 因子和

题目描述 输入两个整数 a 和 b，求$a^b$的因子和。由于结果太大，只要输出它对 9901取模的结果。

输入格式 仅一行，为两个整数 a 和 b。

输出格式 输出一行一个整数表示答案对 9901 取模的结果。

输入输出样例 输入 #1

2 3

输出 #1

15

说明/提示 数据规模与约定 对于全部的测试点，保证 $1\le a\le 5\times 10^7，0\le b\le 5\times 10^7$ 。

求因子的和，比如$2^3=8$，$8$的因子有$1,2,4,8$，和为$15$。我们知道对于$x=p_1^{k_1}{p}_2^{k_2}\cdots p_n^{k_n}$，因子和为$(1+p_1+\cdots +p_1^{k_1})\cdots (1+p_n+\cdots +p_n^{k_n})$。再由等比数列求和公式，上式等于： $$\frac{p{1}^{k+1}-1}{p_1-1}\cdot \frac{p{2}^{k+1}-1}{p_2-1}\cdots \frac{p_n^{k+1}-1}{p_n-1}$$ 这里分子很容易求，因为反正会模9901，用快速幂容易实现。除以p-1当时就不知道怎么处理了，然后看了题解才知道，由费马小定理，当p为素数，a不是p的倍数的时候： $$a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$ 那么： $$a^{p-2}\equiv a^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$ 所以这里直接乘以p的9901-2次方即可。那么实现思路就出来了，先对a进行质因数分解，然后得到$a^b$的质因数分解，再代入上面的公式取模得到结果。代码如下，但还有几个易错点：

这里p存储质因数，k存储次数，res存储最后结果qpow是快速幂取模取质因数的时候只需要穷举到$\sqrt{a}$就可以了，因为大于$\sqrt{a}$的质因数最多只有一个注意费马小定理的条件是a不是p的倍数。当公式里的a是p的倍数，即$p_i-1$是9901的倍数时，不能直接代入(有点像等比数列公比讨论是否为1)。这个时候其实$(1+p_i+\cdots +p_i^{k_i})\equiv k_i+1(\mathrm{m}\mathrm{o}\mathrm{d}9901)$数据范围直接用int会溢出，索性用了long然后我自己最后已知WA样例14，显示读的结果是负数，我也不知道为什么。后来明白了是在计算公式的时候，$p_i^{k+1}$的取模可能是0，减1就变成了-1，所以在最后计算的时候取模要加上mod再取模！ #include <bits/stdc++.h> using namespace std; long mod=9901,a,b,res=1; vector<long> p,k; long qpow(long x,long p){ long res=1; while(p){ if(p&1) res=(x*res)%mod; p>>=1; x=(x*x)%mod; } return res%mod; } int main(){ cin>>a>>b; if(!b){ cout<<1; return 0; } if(!a){ cout<<0; return 0; } long aa=a; for(int i=2;i*i<=a;i++){ if(aa%i==0){ p.push_back(i); k.push_back(0); while(aa%i==0){ aa/=i; k.back()++; } } } if(aa>1){ p.push_back(aa); k.push_back(1); } for(int i=0;i<k.size();i++){ k[i]*=b; } for(int i=0;i<k.size();i++){ if(p[i]%mod==1){ res=res*(k[i]+1)%mod; } else{ res=((res*(qpow(p[i],k[i]+1)-1))%mod+mod)*qpow(p[i]-1,mod-2)%mod; } } cout<<res; return 0; }