题意：
给出数字A和B，要求AB的所有因子（包括AB和1）之和 mod 9901 的结果。
思路：
即使知道公式也得推算一阵子。
很容易知道，先把
分解得到
，那么得到
，那么
的所有因子之和的表达式如下：
我们要做的就是计算出sum%9901的结果。
有两种方法：
（1）直接用快速幂计算对上面sum的第一步推算求结果，在计算过程中顺便取模。
（2）可以根据以下这条公式对上面sum的第二步推算求结果：
也是需要用到快速幂，过程也稍微复杂了些。注意 mb 可能会超过int。
以下是第二种方法的代码：
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=;
const LL mod=;
bool isPrime[N];
LL p[N]; //素数表 int get_all_prime(int n) //筛法求所有[0~n)素数，返回素数表大小
{
memset(isPrime, , sizeof(isPrime));
int cnt=;
for(int i=; i<n; i++)
{
if(!isPrime[i]) continue;
p[cnt++]=i;
for(int j=i*i; j<n; j+=i) isPrime[j]=;
}
return cnt;
} LL _mul(LL a,LL b,LL mod) //a*b要用加法形式运算才不会溢出
{
a%=mod;
LL r=; //结果
while( b )
{
if( b& ) r=(r+a)%mod;
a=(a+a)%mod;
b>>=;
}
return r;
} LL pow(LL a,LL b,LL mod) //快速幂函取模
{
a%=mod;
LL r=; //结果
while( b )
{
if( b& ) r=_mul(r,a,mod);
a=_mul(a,a,mod);
b>>=;
}
return r;
} LL cal(LL A,LL B)
{
LL ans=;
for(int i=; p[i]*p[i]<=A; i++ ) //先求A的所有质因子
{
if(A%p[i]==)
{
int cnt=;
while(A%p[i]==) //全部取光
{
cnt++;
A/=p[i];
}
LL mb=mod*(p[i]-);
ans*=(pow(p[i], cnt*B+, mb)+mb-)%mb/(p[i]-) ; //要防止出现负数
ans%=mod;
}
} if(A>)
{
//如果没有把A成功分解，那么必定是个质数。
//其实也可以写在上面那一步中，只是复杂度就会稍高了。
LL mb=mod*(A-);
ans*=(pow(A, B+, mb)+mb-)%mb/(A-) ; //要防止出现负数
ans%=mod;
} return ans;
} int main()
{
//freopen("input.txt", "r", stdin);
get_all_prime(N);
int A, B;
while(~scanf("%d%d",&A,&B))
printf("%lld\n", cal(A,B) );
return ;
}
AC代码