算法1

等差数列公式 + 快速幂

$A^B的约数之和 = (1 + p_1 + p_1^2 + … + p_1^{a_1})^B * (1 + p_2 + p_2^2 + … + p_2^{a_2})^B * ....$
对于每个质数的部分有 $1 + p_1 + p_1^2 + … + p_1^{a_1} = \frac{p^{n + 1} - 1}{p - 1}$

对$A$分解出每个质数，用快速幂求$p^{n + 1}$，求逆元方式求$\frac{1}{p - 1}$

时间复杂度$O(\sqrt{n} logn)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int mod = 9901;
    static long qmi(int a,int k)
    {
        long res = 1 % mod;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % mod;
            k >>= 1;
            t = t * t % mod;
        }
        return res;
    }
    static long mul(int p,int k)
    {
        if((p - 1) % mod != 0) return (qmi(p,k + 1) - 1 + mod) % mod * qmi(p - 1,mod - 2) % mod;
        else return k + 1;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();

        long res = 1;
        for(int i = 2;i <= a / i;i ++)
        {
            if(a % i == 0)
            {
                int s = 0;
                while(a % i == 0)
                {
                    s ++;
                    a /= i;
                }
                res = res * mul(i,s * b) % mod;
            }
        }
        if(a > 1) res = res * mul(a,1 * b) % mod;
        if(a == 0) res = 0;

        System.out.println(res);
    }
}

算法2

分治 + 快速幂
$k$表示长度，$sum(p,k)$求的是$(1 + p + p^2 + … + p^{k - 1})$

1、$k$是偶数，$sum(p,k) = (p^0 + p^1 + … + p^{\frac{k}{2} - 1}) + (p^{k / 2} + p^{\frac{k}{2}} + p^{{\frac{k}{2} + 1}} + … + p^{k - 1}) $

2、$k$是奇数，$sum(p,k) = sum(p,k - 1) + p^{k - 1}$

时间复杂度 $O(\sqrt{n} lognlogn)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int mod = 9901;
    static long qmi(int a,int k)
    {
        long res = 1 % mod;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % mod;
            k >>= 1;
            t = t * t % mod;
        }
        return res;
    }
    static long sum(int p,int k)
    {
        if(k == 1) return 1;
        if(k % 2 == 0) return (1 + qmi(p,k / 2)) * sum(p,k / 2) % mod;
        else return (qmi(p,k - 1) + sum(p,k - 1)) % mod;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();

        long res = 1;
        for(int i = 2;i < a / i;i ++)
        {
            if(a % i == 0)
            {
                int s = 0;
                while(a % i == 0)
                {
                    s ++;
                    a /= i;
                }
                res = res * sum(i,s * b + 1) % mod;
            }
        }
        if(a > 1) res = res * sum(a,b + 1) % mod;
        if(a == 0) res = 0;

        System.out.println(res);
    }
}