算法1

等比数列+求逆元

时间复杂度

参考文献

C++ 代码

/*
Sn = (anq - a1)/(q-1)
由本题知q = i;
由于有n+1项；
Sn+1 = (an+1q - a1)/(q-1)
因为an = a1q^(n-1)
得
Sn+1 = (a1q^(n+1) - a1)/(q-1);
在由费马小定理
除以一个数并取模，等于乘上这个树得逆元，在取模;
求逆元用快速幂
ksm(x, Mod - 1)
*/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Mod = 9901; 
using LL = long long;
LL ksm(LL a, LL n){
    LL res = 1;
    while(n){
        if(n&1) res = (res%Mod * a%Mod)%Mod;
        a = (a%Mod * a%Mod) % Mod;
        n >>= 1;
    }
    return res;
}

int main(){
    LL A, B;
    cin >> A >> B;
    LL res = 1;
    if(A == 0) res = 0;
    for(int i = 2; i <= A; ++ i){
    if(A % i == 0){
        LL s = 0;
        while(A % i == 0){
            s ++;
            A /= i;
        }

        LL x = i % Mod;
        if(i % Mod == 1)//避免出现为零的情况余数为1的时候逆元为零，不满足条件
            res = res*(B*s + 1) % Mod;
        else res = (res % Mod * (ksm(x, s * B + 1)-1) % Mod * ksm(x - 1, Mod - 2) %Mod) %Mod;

        }
    }
    cout  << res << endl;
    return 0;
}

算法2

分治

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

using ll = long long;
const int Mod = 9901;
int ksm(int a, int n){//快速幂
    int res = 1;
    while(n){
        if(n&1) res = res%Mod * a % Mod;
        a = a % Mod * a % Mod;
        n >>= 1;
    }
    return res;
}

int sum(int p, int n){//分治思想
    if(n == 0) return 1;
    if(n&1) return ((1 + ksm(p, (n+1)/2))* sum(p, (n-1)/2)) % Mod;
    return ((1 + ksm(p, n/2)) * sum(p, n/2 - 1) + ksm(p, n))% Mod; 
}

int main(){
    int A, B;
    int ans = 1;
    cin >> A >> B;
    for(int i = 2; i <= A; ++ i){
        int res = 0;
        while(A % i == 0)res++, A /= i;
        if(res) ans = ans%Mod * sum(i, res * B)%Mod;
    }
    if(A == 0) ans = 0;//这个点很坑
    cout << ans << endl;
    return 0;
}