因子和

题目描述

输入两个正整数a和b，求\(a^b\)的因子和。结果太大，只要输出它对9901的余数。

解法

基本算数定理，每一个数都可以被分解成一系列的素数的乘积，然后你可以分解出因数了。

如何求出因数和呢？我们发现是等比数列，之后我们上等比数列求和公式就好了

\[ S_n = \frac{a_1 \times (1-q^n)}{1-q}=\frac{p_{i}^{c_i+1} -1}{p_i -1} \]

其中我们可以用快速幂和逆元求出来了

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define LL long longusing namespace std;const LL mod = 9901;LL ksm(LL x,LL y) { LL z=1; while(y) { if(y&1) z=(z*x)%mod; y>>=1; x=(x*x)%mod; } return z%mod;}LL to[2],get=1;int main() { LL a=0,b=0,tmp,lim; scanf("%lld%lld",&a,&b); lim=sqrt(a); for(LL i = 2; i <= lim; i ++) { if(!(a%i)) { tmp=0; while(!(a%i)) { a/=i; tmp++; } to[1]=(tmp*b+1); if(i%mod==1) get=get*(tmp+1)%mod; else { to[0]=i%mod; get=get*(ksm(to[0],to[1])-1)*ksm(to[0]-1,mod-2)%mod; } } } if(a!=1) { to[1]=(b+1); if(a%mod==1)get=get*(b+1)%mod; else { to[0]=a%mod; LL k=(ksm(to[0],to[1])-1)*ksm(to[0]-1,mod-2)%mod; get=get*k%mod; } } printf("%lld",get); return 0;}