详见代码:
#include#include #include #include #define MOD 9901// 9901是一个素数 using namespace std;int A, B; // 计算A^B的所有因子的和 int num[50], ex[50], idx; // 记录所有的因子和指数void deal(int x) { idx = -1; for (int i = 2; i <= (int)sqrt(double (x)); ++i) { if (x % i == 0) { ++idx; num[idx] = i; ex[idx] = 0; while (x % i == 0) { ++ex[idx]; x /= i; } } } if (x != 1) { ++idx; num[idx] = x; ex[idx] = 1; } // 分解完成} /*A * x = 1 mod B;A * x - B * y = 1;要求1必须是gcd(A, B)的倍数，由于9901是一个素数，因此只有当A==9901是不符合要求的*/int exgcd(int a, int b,int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int ret = exgcd(b, a % b, x, y); int t = x; x = y; y = t - a/b*y; return ret;}int getinv(int v) { v %= MOD; int a = v, b = MOD, x, y; exgcd(a, b, x, y); x = (x % MOD + MOD) % MOD; return x;}int _pow(int a, int b) { int ret = 1; a %= MOD; while (b) { if (b & 1) { ret *= a; ret %= MOD; } b >>= 1; a *= a; a %= MOD; } return ret;}// 1073741824 // 等比公式是 (num[i]^exp[i])^B = num[i]^exp[i]*B// 其因子和为num[i]^0 + num[i]^1 + ...num[i]^exp[i]*B// 化简之后就是 (num[i]^(exp[i]*B+1)-1)/(num[i]-1)int main() { int ret; while (scanf("%d %d", &A, &B) == 2) { ret = 1; deal(A); // 对A进行分解 for (int i = 0; i <= idx; ++i) { if (num[i] % MOD == 1) { // 这里要进行一下特殊处理,不然就直接去就0的逆元了 ret *= (ex[i]*B+1)%MOD; ret %= MOD; } else { ret *= ((_pow(num[i]%MOD, ex[i]*B+1)-1+MOD)%MOD*getinv(num[i]-1))%MOD; ret %= MOD; } } printf("%d\n", ret); } return 0; }