记录编号	411307	评测结果	AAAAAAAAAAAAA
题目名称	[POJ 1845] Sumdiv	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-06-04 20:18:15	内存使用	4.45 MiB

#include <cstring>
#include <cstdio>
#include <cmath>
#define MOD 9901
#define MAXP 7072
 
#define ll long long
#define mul(x, y, m) (int)(((ll)(x) * (ll)(y)) % m)
 
int fastpow(int a, int p, int mod) {
	int base = a, ans = 1;
	while(p) {
		if(p & 1) ans = mul(ans, base, mod);
		base = mul(base, base, mod);
		p >>= 1;
	}
	return ans;
}

int N, P;
int A[MAXP+10], Apow[MAXP+10], An = 0;

int arrsum(int p, int n) {
	if(n == 0) return 1;
	if(n & 1) return ((ll)arrsum(p, n/2) * (1 + fastpow(p, n/2+1, MOD))) % MOD;
	return ((ll)arrsum(p, n/2-1) * (1 + fastpow(p, n/2+1, MOD)) + fastpow(p, n/2, MOD)) % MOD;
}
 
int main() {
	freopen("sumdiv.in", "rt", stdin);
	freopen("sumdiv.out", "wt", stdout);
 
	int i, ans = 1, tmp, rev;
	scanf("%d%d", &N, &P);
	if(N == 0) ans = 0;
	else {
		for(i=2;i*i<=N;i++) if(!(N % i)) {
			A[An] = i;
			while(!(N % i)) {
				Apow[An]++;
				N /= i;
			}
			
			Apow[An] *= P;
			An++;
			if(N == 1) break;
		}
		if(N != 1) {
			A[An] = N; Apow[An] = P; An++;
		}
		
		for(i=0;i<An;i++) {
			ans = mul(ans, arrsum(A[i], Apow[i]), MOD);
		}
	}
	printf("%d", ans);
}