题目描述

假设现在有两个自然数A和B，S是AB的所有约数之和。

请你求出S mod 9901的值是多少。

输入格式
在一行中输入用空格隔开的两个整数A和B。

输出格式
输出一个整数，代表S mod 9901的值。

数据范围
$0≤A,B≤5×10^7$

输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。

感谢@hkr04大佬指出本题目代码效率有点低,导致TLE.
现在已经加入剪枝优化AC了,大家可以放心食用.

正解

(数学(质因数分解，唯一分解定律，约数和公式)，分治递归)

数学类分析

1. 质因数分解，就是将一个数分解成为 ${p_1}^{c1} \times {p_2}^{c_2} \times … \times {p_n}^{c_n}$ 比如说$24={2}^{3}\times{3}^{1}$
2. 唯一分解定律，就是字面意思
3. 约数和公式，如下文所示
   ${A}^{B}=(1 \+ {p_1}^{1} \+ {p_1}^{2} \+ ..... \+ {p_1}^{B \* c_1}) \times (1 \+ {p_2}^{2} \+ ..... \+ {p_n}^{B \times c_2}$)
   $sum(p,c)= {1} \+ {p} \+ {p^2} \+ … \+ {p^c}$
   然后呢我们可以通过分类以及乘法中的提取公因式法，将sum函数中c为奇数的公式和sum函数中c为偶数的公式推出。具体参考《算法竞赛进阶指南》，亦可以看我的cpp代码中的sum函数。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 9901
int a,b;
int ksm(int a,int b)//快速幂函数
{
    int ans=1;
    a%=Mod;
    while(b)
    {
        if (b&1)
            ans=ans%Mod*a;
        a=a%Mod*a%Mod;
        b>>=1;
    }
    return ans;
}
long long sum(int p,int c)
{
    if (c==0)
        return 1;
    if(c&1)
        return ((1+ksm(p,(c+1)>>1))*sum(p,(c-1)>>1))%Mod;//奇数的情况下
    else
        return ((1+ksm(p,c>>1))*sum(p,(c>>1)-1)+ksm(p,c))%Mod;//偶数的情况下
}
int main()
{
    cin>>a>>b;
    int ans=1;
    for (int i=2;i<=a;i++)
    {
        int s=0;
        while(a%i==0)
        {
            s++;
            a/=i;
        }
        if (s)//这句话剪枝.然后就TLE变成了AC.by POJ
            ans=ans*sum(i,s*b)%Mod;
    } 
    if (a==0)
        cout<<0<<endl;//特判的情况，这里非常的阴毒，出题人用心险恶
    else
        cout<<ans<<endl;
    return 0;
}