Sumdiv poj 1845
等比数列求和并取模,非逆元方法

const int  M = 9901;
long long qpow(long long a,long long b)
{
    a %= M;
    long long ans = 1;
    while(b>0)
    {
        if(b&1)
        ans = ans*a%M;
        a = a*a%M;
        b >>= 1;
    }
    return ans;
}
//素数表
const int LEN = 1e4+100;
bool vis[LEN];
int Prime[LEN];
int cnt = 1;
void init(void)
{
    int n = LEN - 1;
    for(int i = 2;i <= n; ++i)
    {
        if(!vis[i])
        {
            Prime[cnt++] = i;
            for(int j = i + i; j <= n; j += i)
             vis[j] = true;
        }
    }
}
int Fract[LEN][2];
int num;
void getPrime(long long n)
{
    num = 0;
    for(int i = 1;Prime[i] * Prime[i] <= n; ++i)
    {
        if(n % Prime[i]==0)
        {
            Fract[++num][0] = Prime[i];
            Fract[num][1] = 0;
            while(n%Prime[i]==0)
            {
                Fract[num][1]++;
                n /= Prime[i];
             }
        }
    }
    if(n != 1)
    {
        Fract[++num][0] = n;
        Fract[num][1] = 1;
    }
}
long long Sum(long long p,long long a)//某一个因子求和
{
    if(p == 0)
      return 0;
    if(a == 0)
      return 1;
    if(a&1)
        return (1 + qpow(p,a/2+1)) % M * Sum(p,a/2) % M;
    return ((1 + qpow(p,a/2+1)) % M * Sum(p,a/2-1) % M + qpow(p,a/2))%M;
}

int main(void)
{// cout<<qpow(2,10)<<endl;

   std::ios::sync_with_stdio(false);
   init();
   int A,B;
   while(cin>>A>>B)
   {
      getPrime(A);
      long long ans = 1;
      for(int i = 1;i <= num; ++i)
         ans = (ans*Sum(Fract[i][0],B*Fract[i][1]))%M;
      cout<<ans<<endl;
   }
   return 0;
}

2 变换 + 逆元求解 

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 9901;
long long muti(long long a,long long b,long long Mod)//二分乘法
{
    long long ans = 0;
    while(b > 0)
    {
        if(b&1)
        ans = (ans + a) % Mod;
        a = (a + a) % Mod;
        b >>= 1;
    }
    return ans;
}
long long qpow(long long q,long long a,long long Mod)
{
    q %= Mod;
    a += 1;
    long long ans = 1;
    while(a>0)
    {
        if(a&1)
            ans = muti(ans,q,Mod);
        q = muti(q,q,Mod);
        a >>= 1;
    }
    return (ans-1+Mod)%Mod;
}
int main()
{
// cout << "Hello world!" << endl;
    long long  A,B;
    while(cin>>A>>B)
    {
// if(A == 0)
// {
// cout<<0<<endl;
// break;
// }
        long long ans = 1;
        for(long long  i = 2;i * i <= A; ++i)
        {
            if(A%i==0)
            {
                int num = 0;
                while(A%i == 0)
                {
                    num++;
                    A /= i;
                }
                ans = ans * (qpow(i,B*num,(i-1)*M) / (i-1) % M) % M;
            }
        }
        if(A!=1)
         ans = ans * (qpow(A,B,(A-1)*M)/(A-1)%M) % M;
        cout<<ans<<endl;
    }
    return 0;
}