整数分解定理： A = p1^k1 * p2^k2 * … * pn^kn; 整数分解后的约数和公式： sum=(1+p1+p1^2 +…+p1^k1) * (1+p2+p2^2+ … +p2^k2) * … * (1+pn+pn^2+ …+pn^kn)； 递归二分求等比数列： 1+p+p^2 +…+p^n; n为奇数时，(1 + p + p^2 +…+ p^(n/2)) * (1 + p^(n/2+1))； n为偶数时，(1 + p + p^2 +…+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);或者提一个p变成奇数p*(1 + p + p^2 +…+ p^(n/2)) * (1 + p^(n/2+1))+1;
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.StreamTokenizer; public class MainF { static int mod = 9901; public static void main(String[] args) throws IOException { StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(System.out); sc.nextToken(); long a = (long)sc.nval; sc.nextToken(); long b = (long)sc.nval; long res = 1; for(int i=2;i*i<=a;i++) { long n = 0; while(a%i==0) { n++; a /= i; } if(n!=0) res = res*sum(i,n*b); } if(a!=1) { res = res*(sum(a,b)); } if(a>0) { out.println(res%mod); }else { out.println(0); } out.flush(); } public static long sum(long p,long n) { //递归二分求等比 if(n==0) return 1; if(n%2==0) { return (p%mod*sum(p,n-1)%mod+1)%mod; }else { return (1+pow(p,n/2+1))*sum(p,n/2)%mod; } } public static long pow(long p,long n) { long res = 1; p = p%mod; while(n!=0) { if((n&1)==1) { res = res*p%mod; } n >>= 1; p =p*p%mod; } return res%mod; } }