题意简述:
求$a^b$的所有因子和
解题思路:
既然要求因子和,那我们必然要先分解质因数
根据整数的唯一分解定理,整数a进行质因数分解对应的式子唯一,有:
$$a = p_1^{k_1} * p_2^{k_2} *p_3^{k_3}* … * p_n^{k_n}$$
又因为本题要分解的是$a^b$,所以上面的式子又可以写成这样:
$$a^b= p_1^{k_1*b} * p_2^{k_2*b} *p_3^{k_3*b}* … * p_n^{k_n*b}$$
证明很简单,就是把上面第一个式子乘上$b$次即可得第二个式子
接下来我们要求的是因子和,
所以就有:
$$ans= (1+p_1^1 + p_1^2 +p_1^3+ … + p_1^{k_1*b})*(1+p_2^1 + p_2^2 +p_2^3+ … + p_1^{k_2*b})*…*(1+p_n^1 + p_n^2 +p_n^3+ … + p_n^{k_n*b})$$
对于上面的式子是不是有点熟悉?
对,你没有看错,就是等比数列之间的乘积
根据等比数列求和公式:
$$sum=\frac{p^{n}-1}{p-1}$$
我们就能求出各数列的和,
对于$p^{n+1}$,我们用快速幂求
又因为本题要求的答案要对9901取模
故我们又可以通过逆元将除$p-1$转化为乘$p-1$的逆元
接下来要求逆元,根据定义,在$mod\ p$的意义下,对于一个整数$a$,有:
$$a*x≡1(mod\ p)$$
$x$即为$a$的逆元,反之成立
注意此处的$a,p$均与上文的意义不同,仅作为公式中的未知数
当$a,p$不互质时,逆元不存在,即上面的式子要满足:
$$gcd(a,p)=1$$
那么这个$x$怎么求?
那我们再引入一个定理,费马小定理:
假如$a$是一个整数,$p$是一个质数,那么当$a$是$p$的倍数时,有:
$$a^p≡a(mod\ p)$$
当$a$不是$p$的倍数时,有:
$$a^{p-1}≡1(mod\ p)$$
对于本题,显然我们要用的是第二种情况,第二种情况又可以变形为:
$$a*a^{p-2}≡1(mod\ p)$$
上式恰好对应逆元的定义式,故$a$在$mod\ p$意义下的逆元为$a^{p-2}$
$a^{p-2}$我们用快速幂即可求得
那逆元不存在怎么办,不用担心,因为对应上面的式子$p-1$,有:
$$(p-1) \ mod \ 9901=0$$
即:
$$p \ mod \ 9901=1$$
所以该等比数列之和($mod\ p$意义下)为:
$$sum= 1+({p\ mod\ 9901})^1 +({p\ mod\ 9901})^2 +({p\ mod\ 9901})^3+ … + ({p\ mod\ 9901})^{n}$$
即:
$$sum=1+n$$
至此,本题就分析完了
代码实现:
1 |
|