【题目链接】
【算法】
不妨先将A分解质因数
A = p1^q1p2^p2p3^p3..pn^qn
那么,A^B = p1^q1Bp2^q2B...pn^qnB
根据约数和定理，A^B的约数和就是 ：
(p1^0 + p1^1 + .. p1^q1B)(p2^0 + p2^1 + ... p2^q2B) ... (pn^0 + pn^1 + ... + pn^qnB)
显然可以用等比数列求和来做，注意特判逆元不存在的情况
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define P 9901 long long i,len,ans,A,B; struct info { long long p,q; } d[100010]; inline long long power(long long a,long long n) { long long ans = 1,b = a; while (n) { if (n & 1) ans = (ans * b) % P; b = (b * b) % P; n >>= 1; } return ans; } inline long long inv(long long x) { return power(x,P-2); } inline long long calc(long long a,long long n) { return (power(a,n+1) - a % P + P) % P * inv(a-1) % P; } int main() { scanf("%lld%lld",&A,&B); for (i = 2; i <= sqrt(A); i++) { if (A % i == 0) { d[++len] = (info){i,0}; while (A % i == 0) { A /= i; d[len].q++; } } } if (A > 1) d[++len] = (info){A,1}; for (i = 1; i <= len; i++) d[i].q *= B; ans = 1; for (i = 1; i <= len; i++) { if ((d[i].p - 1) % P == 0) ans = (ans * (d[i].q + 1)) % P; else ans = (ans * (calc(d[i].p,d[i].q) + 1)) % P; } printf("%lld ",ans); return 0; }