约数之和
题目描述
思路分析
对A分解质因数，所以 A = p 1 c 1 ∗ p 2 c 2 ∗ ⋯ p n c n A=p_1^{c_1}*p_2^{c_2}*\cdots p_n^{c_n} A=p1c1∗p2c2∗⋯pncn，那么 A B A^B AB就可以表示为： A B = p 1 B ∗ c 1 ∗ p 2 B ∗ c 2 ∗ ⋯ p 3 B ∗ c n A^B=p_1^{B*c_1}*p_2^{B*c_2}*\cdots p_3^{B*c_n} AB=p1B∗c1∗p2B∗c2∗⋯p3B∗cn，由约数个数定理可知，对于 p 1 B ∗ c 1 p_1^{B*c_1} p1B∗c1来说。它的因子有： p 1 0 、 p 1 1 、 ⋯ , p 1 B ∗ c 1 p_1^0、p_1^1、\cdots ,p_1^{B*c_1} p10、p11、⋯,p1B∗c1,共有 ( B ∗ c 1 + 1 ) (B*c_1+1) (B∗c1+1)个因子。对于 p n B ∗ c n p_n^{B*c_n} pnB∗cn来说，它的因子有： p n 0 、 p n 1 、 ⋯ p n B ∗ c n p_n^0、p_n^1、\cdots p_n^{B*c_n} pn0、pn1、⋯pnB∗cn，共有 ( B ∗ c n + 1 ) (B*c_n+1) (B∗cn+1)个因子。根据乘法分配律， A B A^B AB的所有约数之和就是： ( 1 + p 1 1 + p 1 2 + ⋯ + p 1 B ∗ c 1 ) ( 1 + p 2 1 + p 2 2 + ⋯ + p 2 B ∗ c 2 ) ⋯ ( 1 + p n 1 + p n 2 + ⋯ + p n B ∗ c n ) (1+p_1^1+p_1^2+\cdots +p_1^{B*c_1})(1+p_2^1+p_2^2+\cdots +p_2^{B*c_2})\cdots (1+p_n^1+p_n^2+\cdots +p_n^{B*c_n}) (1+p11+p12+⋯+p1B∗c1)(1+p21+p22+⋯+p2B∗c2)⋯(1+pn1+pn2+⋯+pnB∗cn)。该式子中每个括号内都是等比数列，如果使用等比数列求和，即用 S n = a 1 ( 1 − q n ) ( 1 − q ) S_n=\dfrac {a_1(1-q^n)}{(1-q)} Sn=(1−q)a1(1−qn)
那么就需要做除法。而且题目还要求对9901取模，但是mod运算它只对加法、减法、乘法具有分配律，而对除法没有分配律。因此，不能直接分别对分子取模、分母取模后，再做除法取模，即 a b m o d p ≠ a m o d p b m o d p m o d p \dfrac {a}{b}\quad mod \quad p\neq \dfrac {a\quad mod\quad p}{b\quad mod\quad p}mod \quad p bamodp=bmodpamodpmodp。因此，我们需要转换一种思路，可以使用分治算法对等比数列进行求和，曲线救国，避免使用除法来取模。
分治算法是把一个问题分解成若干规模更小的同类子问题，对这些子问题进行递归求解，然后在回溯时通过这些子问题的解推导出原问题的最终解。
将问题转换为使用分治算法求： s u m ( p , c ) = 1 + p 1 + p 2 + ⋯ + p c sum(p,c)=1+p^1+p^2+\cdots +p^c sum(p,c)=1+p1+p2+⋯+pc=?
- 当c是奇数时， s u m ( p , c ) = ( 1 + p 1 + ⋯ + p c − 1 2 ) + ( p c + 1 2 + ⋯ + p c ) sum(p,c)=(1+p^1+\cdots +p^{\dfrac {c-1}{2}})+(p^{\dfrac {c+1}{2}}+\cdots +p^c) sum(p,c)=(1+p1+⋯+p2c−1)+(p2c+1+⋯+pc)= ( 1 + p 1 + ⋯ + p c − 1 2 ) + p c + 1 2 ( 1 + p 1 + ⋯ + p c − 1 2 ) (1+p^1+\cdots +p^{\dfrac {c-1}{2}})+p^{\dfrac {c+1}{2}}(1+p^1+\cdots +p^{\dfrac {c-1}{2}}) (1+p1+⋯+p2c−1)+p2c+1(1+p1+⋯+p2c−1)= ( 1 + p c + 1 2 ) ( 1 + p 1 + ⋯ + p c − 1 2 ) (1+p^{\dfrac {c+1}{2}})(1+p^1+\cdots +p^{\dfrac {c-1}{2}}) (1+p2c+1)(1+p1+⋯+p2c−1)= ( 1 + p c + 1 2 ) ∗ s u m ( p , c − 1 2 ) (1+p^{\dfrac {c+1}{2}})*sum(p,\dfrac {c-1}{2}) (1+p2c+1)∗sum(p,2c−1)。
- 当c是偶数时， s u m ( p , c ) = ( 1 + p 1 + ⋯ + p c − 1 ) + p c sum(p,c)=(1+p^1+\cdots +p^{c-1})+p^c sum(p,c)=(1+p1+⋯+pc−1)+pc，因为c是偶数，所以c-1就是奇数，把c-1带入已经推导出来的奇数式子中可以得到： s u m ( p , c − 1 ) = ( 1 + p c 2 ) ∗ s u m ( p , c 2 − 1 ) sum(p,c-1)=(1+p^{\dfrac {c}{2}})*sum(p,\dfrac {c}{2}-1) sum(p,c−1)=(1+p2c)∗sum(p,2c−1)。因此， s u m ( p , c ) = ( 1 + p c 2 ) ∗ s u m ( p , c 2 − 1 ) + p c sum(p,c)=(1+p^{\dfrac {c}{2}})*sum(p,\dfrac {c}{2}-1)+p^c sum(p,c)=(1+p2c)∗sum(p,2c−1)+pc。
时间复杂度分析
每次分治之后，问题规模就会缩小一半，然后再运用快速幂算法，就可以再 O ( l o g c ) O(logc) O(logc)的时间内求出等比数列的和。
代码如下：
#include<iostream>
using namespace std;
const int mod=9901;
//利用快速幂算法求出a^b%mod
int qmi(int a,int b)
{
int ans=1;
a=a%mod; //因为有可能a很大，那么执行下面的a=a*a%mod语句时，a*a有可能溢出，所以需要先取模一下。
while(b)
{
if(b&1)
ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
//求出等比数列之和
int sum(int p,int c)
{
if(c==0) //如果c为0，那么p^c=p^0=1，直接返回结果1就好了
return 1;
if(c%2) //如果c是奇数，则带入推导出来的奇数公式
return ((1+qmi(p,(c+1)/2))*sum(p,(c-1)/2))%mod;
else //如果c是偶数，则带入推导出来的偶数公式
return ((1+qmi(p,c/2))*sum(p,(c/2-1))+qmi(p,c))%mod;
}
int main()
{
int a,b;
cin >>a>>b;
int ans=1;
//试除法分解质因子
//for循环先对2到sqrt(n)之内的数进行分解质因子
for(int i=2;i*i<=a;i++) //i相当于公式中的p，即质因子
{
int s=0; //记录指数 s相当于公式中的Ci(比如C1、C2...)
while(a%i==0)
{
a/=i;
s++;
}
ans=ans*sum(i,s*b)%mod; //s*b相当于公式中的c
}
//如果退出for循环后，a>1，说明a有且仅有一个大于sqrt(n)的质因子(有可能是a自身)。说明此时的a并不能被sqrt(n)以内的数整除，那么a它的指数就只能是1了。即a^1。
//所以公式中的c=b*1，即c=b。
if(a>1)
ans=ans*sum(a,b)%mod;
//因为题目说了a,b不能同时为0，但是有可能a为0，因为0的任何方都是0，所以，此时结果应该为0，而不是初始的ans=1
if(a==0)
ans=0;
printf("%d\n",ans);
return 0;
}