wrong 做法

看到这个题，最开始的想法是想通过乘法快速幂先求出A的B次方，然后再利用二分的思想求结果的约数，最后将约数加和取模
，但是很不幸，木有通过，wrong answer。顿觉此题不能蛮做，有简便方法。

C++ 代码

//感觉是一道综合题,先用快速幂求出A的B次方，然后再求ret的的约数，然后再求结果

#include<iostream>
using namespace std;
#include<set>

typedef long long ll;
ll a,b,sum;
set<int> s;

ll quick(ll a,ll b)
{
    // ll e=1;
    //定义幺元
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}

int main(){
    cin>>a>>b;
    ll ret=quick(a,b);
    for(ll i=1;i*i<ret;i++)
    {
        if(ret%i==0) s.insert(i),s.insert(ret/i);
    }

    //ll s=0;
    set<int>::iterator it=s.begin();
    while(it!=s.end())
    {   
        sum=(sum+(*it))%9901;
        it++;
    }
    cout<<sum<<endl;
    return 0;
}

灿神的思路（“又是一道小学奥数题.........”）

C++ 代码

//灿神做法
#include<iostream>
using namespace std;
const int mod=9901;

//快速幂
int quick(int a,int b)
{
    int res=1;
    a=a%mod;
    while(b)
    { 
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

//sum函数用来求某个数的幂次项的等比数列的和
int sum(int p,int k)
{
    //k如果是奇数的话，从0到k即为偶数个数
    if(k==0) return 1;
    //k是偶数的时候，则我们(k-1)是奇数，即(k-1)项是偶数,则我们可以把第k项
    //单独把p拿出来,然后对(k-1)再调用sum
    if(k%2==0)
    {
        //这里少了个p的0次方，所以把1加上
        return (p%mod*sum(p,k-1)+1)%mod;
    }
    //否则k如果是奇数，则质因数有(k+1)即偶数项，就去套我们的公式
    return (1+quick(p,k/2+1))*sum(p,k/2)%mod;
}

int main(){

    int A,B;
    cin>>A>>B;
    int res=1;

    //这里是想看i是不是质因数，以及得出i的幂次
    //比如，对于12，可以分解成2^2*3
    for(int i=2;i<=A;i++)
    {
        int s=0;
        //这里的操作是求当我们的质因数是i的时候，它的质因数的幂次项能到几
        while(A%i==0)
        {
            s++;
            A/=i;
        }
        //i,s即相当于我们的质因数以及它的幂次项，即pk和k
        if(s) res=res*sum(i,s*B)%mod;
    }
    //ifA为0的话，那么res=0，。。。。？？？A什么时候为0呢？？？？？
    if(!A) res=0;
    cout<<res<<endl;
    return 0;
}