题意两个数A和B。让S等于 $_math_inline$A^B$math_inline_$ 的所有因子的和，输出S%9901
由分解素因数可知 $_math_inline$A=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$math_inline_$
那么 $_math_inline$A^B=p_1^{a_1B}p_2^{a_2B}...p_k^{a_kB}$math_inline_$
那么 $_math_inline$S=(1+p_1+p_1^2+...+p_1^{a_1B})\times(1+p_2+p_2^2+...+p_2^{a_2B})\times...\times(1+p_k+p_k^2+...+p_k^{a_kB})$math_inline_$
对等比数列求和可得： $_math_inline$S=\frac{p_1^{a_1B+1}-1}{p_1-1}\times\frac{p_2^{a_2B+1}-1}{p_2-1}\times ... \frac{p_k^{a_kB+1}-1}{p_k-1}$math_inline_$
由于有取余操作，那么我们可以通过逆元快速求得每一个分式取余mod的结果
求逆元一般公式(条件b|a)： $_math_inline$ANS=\frac{a}{b}\text{mod}m=\frac{a\text{mod}(mb)}{b}$math_inline_$
Code
1/**
2 * author: Akvicor
3 * created: 2019-08-02 10-38-51
4**/
5
6#include <cstdio>
7#include <cstring>
8#include <iomanip>
9#include <ctime>
10#include <algorithm>
11#include <iostream>
12#include <string>
13#include <vector>
14#include <stack>
15#include <bitset>
16#include <complex>
17#include <cstdlib>
18#include <cmath>
19#include <set>
20#include <list>
21#include <deque>
22#include <map>
23#include <queue>
24
25using namespace std;
26
27#ifdef DEBUG
28#define FAST_IO 17
29#else
30#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
31#define endl '\n'
32#endif
33
34#define rep(i, n) for(int i = 0; i < (n); ++i)
35#define reep(i, n) for(int i = 0; i <= (n); ++i)
36#define lop(i, a, n) for(int i = a; i < (n); ++i)
37#define loop(i, a, n) for(int i = a; i <= (n); ++i)
38#define per(i, a, n) for(int i = a; i >= n; --i)
39#define prec(x) fixed << setprecision(x)
40#define ms(s, n) memset(s, n, sizeof(s))
41#define all(v) (v).begin(), (v).end()
42#define sz(x) ((int)(x).size())
43#define mp(x, y) make_pair(x, y)
44#define pb(x) push_back(x)
45#define fi first
46#define se second
47#define MOD(x) const int MOD = (int)x
48#define MAXN(x) const int MAXN = (int)x + 10
49
50typedef long long LL;
51typedef unsigned long long ULL;
52typedef pair<int, int> PII;
53typedef vector<int> VI;
54typedef vector<PII> VII;
55typedef pair<LL, LL> PLL;
56typedef vector<LL> VL;
57typedef vector<PLL> VLL;
58
59const double EPS = 1e-6;
60const double PI = acos(-1.0);
61const int INF = 0x3f3f3f3f;
62const LL LINF = 0x7f7f7f7f7f7f7f7f;
63
64namespace SOL{
65
66/** >------- Akvicor's Solution -------< **/
67
68MOD(9901);
69MAXN(1e4);
70
71LL a, b;
72bool prime[MAXN];
73int p[MAXN];
74int cnt;
75
76LL mult_mod(LL a, LL b, LL m){
77 a %= m;
78 b %= m;
79 LL ret = 0;
80 LL tmp = a;
81 while(b){
82 if(b&1){
83 ret += tmp;
84 if(ret > m) ret -= m;
85 }
86 tmp <<= 1;
87 if(tmp > m) tmp -= m;
88 b >>= 1;
89 }
90 return ret;
91}
92
93LL quick_mod(LL a, LL n, LL mod){
94 LL ret = 1;
95 LL temp = a % mod;
96 while(n){
97 if(n & 1) ret = mult_mod(ret, temp, mod);
98 temp = mult_mod(temp, temp, mod);
99 n >>= 1;
100 }
101 return ret;
102}
103
104void isprime(){
105 cnt = 0;
106 ms(prime, true);
107 for(int i = 2; i < MAXN; ++i){
108 if(prime[i]){
109 p[cnt++] = i;
110 for(int j = i+i; j < MAXN; j += i)
111 prime[j] = false;
112 }
113 }
114}
115
116void solve(){
117FAST_IO;
118cin >> a >> b;
119isprime();
120
121LL ans = 1;
122for(int i = 0; p[i]*p[i] <= a; ++i){
123 if(a % p[i] == 0){
124 LL num = 0;
125 while(a % p[i] == 0){
126 ++num;
127 a /= p[i];
128 }
129 LL M = (p[i] - 1) * MOD;
130 ans *= (quick_mod(p[i], num*b+1, M) - 1) / (p[i]-1);
131 ans %= MOD;
132 }
133}
134if(a > 1){
135 LL M = (a - 1) * MOD;
136 ans *= (quick_mod(a, b+1, M) - 1) / (a-1);
137 ans %= MOD;
138}
139
140cout << ans << endl;
141
142}
143
144/** >----------------------------------< **/
145
146}
147
148int main(){
149
150#ifdef DEBUG
151 int DEBUGCNT = 0;
152 clock_t DEBUGstart, DEBUGfinish;
153 double DEBUGduration;
154 cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
155 while (DEBUGCNT < 70) {
156 cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
157 DEBUGstart = clock();
158#endif
159
160 SOL::solve();
161
162#ifdef DEBUG
163 DEBUGfinish = clock();
164 DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
165 cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
166 if (cin.eof()) break;
167 if (!cin.good()) break;
168 if (cin.fail()) break;
169 if (cin.bad()) break;
170 ++DEBUGCNT;
171 }
172 cout << ">----------------------------------<" << endl << endl;
173#endif
174
175 return 0;
176}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。