Link：click here
The question：求A的B次方的所有因子的和模9901的值
Solution：求出A的素因子x和个数y，每个素因子有y+1种取法，所有因子的总个数为 （1+y[1]）×（1+y[2]）×⋅⋅⋅×（1+y[n]）
所以，所有因子的和为：（1+x[1]+x[1]2+⋅⋅⋅x[1]y[1]）×（1+x[2]+x[2]2+⋅⋅⋅x[2]y[2]）×（1+x[3]+x[3]2+⋅⋅⋅x[3]y[3]）×⋅⋅⋅×（1+x[n]+x[n]2+⋅⋅⋅+x[n]y[n]）
Conclusion：求等比数列和的时候，并不能用公式求，需要二分来求。因为快速幂取模后，1−qn 会出现误差，不等于正确的结果，如果不去模又会溢出。
Code： #include using namespace std; const long long mod = 9901; long long quick(long long x, long long y) { long long s = 1; for (; y; y >>= 1, x = x * x % mod) if (y & 1) s = s * x % mod; return s; } long long sum(long long q, long long n) { if (!n) { return 1; } if (n & 1)//odd { return ((1 + quick(q, n / 2 + 1)) * sum(q, n / 2)) % mod; } else//even { return ((1 + quick(q, n / 2 + 1)) * sum(q, n / 2 - 1) + quick(q, n / 2)) % mod; } } long long Sum(long long q, long long n) { return (1 - quick(q, n + 1))/ (1 - q); } int main() { long long A, B; while(~scanf("%lld%lld", &A, &B)) { int c = 0; long long ans = 1; for (int i = 2; i * i <= A; i++) { int num = 0; if (A % i == 0) { while (A % i == 0) { A /= i; num++; } } if (num) ans = ans * Sum(i, B * num) % mod; } if (A != 1) { ans = ans * Sum(A, B) % mod; } printf("%lld ", ans % mod); } return 0; }