题目链接：https://vjudge.net/problem/POJ-1845

题意：求A的B次方的所有因子（包括1）的和对9901的模。

思路：首先对A利用唯一分解定理得A=p1^x1*p2^x2*...*pn^xn，则A^B=p1^B*x1*p2^B*x2*...*pn^B*xn。且其所有因子的和等于：

　　　　(1+p1¹+...+p1^B*x1)*(1+p2¹+...+p2^B*x2)*...*(1+pn¹+...+pn^B*xn)。

　　　对其中的1+pi¹+...+pi^B*xi，可以用等比数列的求和公式来计算，即(pi^B*xi+1-1)/(pi-1)，需要计算除法对9901的模，所以需用逆元。注意到这里不建议使用费马小定　　　理或扩展欧基里德来求逆元，因为不能确保互斥，所以选择最方便的a/b % m=a%(b*m)/b，其中b|a。但要注意的是用快速幂时乘法可能超出LL的范围，所以用到　　　了快速乘法。

AC代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 typedef long long LL; 6 const LL Mod=9901; 7 int A,B; 8 LL ans=1,M; 9 10 LL qmul(LL a,LL b){11     LL ret=0;12     while(b){13         if(b&1) ret=(ret+a)%M;14         b>>=1;15         a=(a+a)%M;16     }17     return ret;18 }19 20 LL qpow(LL a,LL b){21     LL ret=1;22     while(b){23         if(b&1) ret=qmul(ret,a);24         b>>=1;25         a=qmul(a,a);26     }27     return ret;28 }29 30 int main(){31     scanf("%d%d",&A,&B);32     for(int i=2;i*i<=A;++i){33         if(A%i==0){34             int num=0;35             while(A%i==0){36                 A/=i;37                 ++num;38             }39             M=Mod*(i-1);40             ans=ans*(qpow(i,num*B+1)-1LL+M)/(i-1)%Mod;41         }42     }43     if(A!=1){44         M=Mod*(A-1);45         ans=ans*(qpow(A,B+1)-1LL+M)/(A-1)%Mod;46     }47     printf("%lld\n",ans);48     return 0;49 }