Sumdiv
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).
Input
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
Output
The only line of the output will contain S modulo 9901.
Sample Input
2 3
Sample Output
15
Hint
2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
Source
题目类型：素因子分解+逆元+整数快速幂取模
算法分析：首先使用Euler筛将素数预打表，然后从小到大判断每个素数在a中出现的指数值，然后带入约数和公式边模边求解，这里使用了一个求逆元非常好的公式：a / b mod (p) = a mod (mb) / m，由于指数比较大，所以要使用整数快速幂来加速运算
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 1000000000 + 7; const int maxn = 10000 + 666; bool prime[maxn]; int primelist[maxn], prime_len; void GetPrime () { memset (prime, true, sizeof (prime)); prime_len = 0; int i; for (i = 2; i <= maxn; i++) { if (prime[i]) primelist[prime_len++] = i; int j; for (j = 0; j < prime_len; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } long long mult_mod (long long a,long long b,long long mod) { a %= mod; b %= mod; long long ans = 0; long long temp = a; while (b) { if (b & 1) { ans += temp; if (ans > mod) ans -= mod;//直接取模慢很多 } temp <<= 1; if (temp > mod) temp -= mod; b >>= 1; } return ans; } long long pow_mod (long long a,long long n,long long mod) { long long ans = 1; long long temp = a % mod; while (n) { if (n & 1) ans = mult_mod (ans, temp, mod); temp = mult_mod (temp, temp, mod); n >>= 1; } return ans; } long long GetFactorSum (long long a, long long b, long long mod) { long long ans = 1; for (long long i = 0; primelist[i] * primelist[i] <= a; i++) { if (a % primelist[i] == 0) { long long tempsum = 0; while (a % primelist[i] == 0) { tempsum++; a /= primelist[i]; } long long m = (primelist[i] - 1) * mod; ans *= (pow_mod (primelist[i], tempsum * b + 1, m) + m - 1) / (primelist[i] - 1); ans %= mod; } } if (a > 1) { long long m = (a - 1) * mod; ans *= (pow_mod (a, b + 1, m) + m - 1) / (a - 1); ans %= mod; } return ans; } int main() { // ifstream cin ("aaa.txt"); GetPrime (); long long a, b; while (cin >> a >> b) { cout << GetFactorSum (a, b, 9901) << endl; } return 0; } |
- « 上一篇：poj1811
- poj1861：下一篇 »