记录编号	567083	评测结果	AAAAAAAAAAAAA
题目名称	[POJ 1845] Sumdiv	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2021-11-22 13:24:14	内存使用	12.15 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ull;
ull a,b;
struct Primes {
	ull val;
	ull num;
	Primes() {
		val = num = 0;//val:the value of this prime
		//num:the number which appeared in the sum
	}
	Primes(ull val,ull num):val(val),num(num){}
}p[1000005];
int cnt = 0;
const ull mod = 9901;
ull Power(ull k,ull x) {
    ull now = 1;
    for(;x;x >>= 1) {
        if(x & 1) {
            (now *= k) %= mod;
        }
        (k *= k) %= mod;
    }
    return now;
}
void get_Primes(ull n) {
	for(ull i = 2;i * i <= n;++ i) {
		if(n % i == 0) {                               
			p[++ cnt].val = i;
			while(n % i == 0) {
				++ p[cnt].num;
				n /= i;
			}
		}
	}                     
	if(n > 1) {
		p[++ cnt].val = n;
		p[cnt].num = 1;
	}
	return ;
}
int main() {
	freopen("sumdiv.in","r",stdin);
	freopen("sumdiv.out","w",stdout);
	scanf("%lld%lld",&a,&b);
	if(!a) {
	    puts("0");
	    return 0;
    }
	ull ans = 1;
	get_Primes(a);         
	for(int i = 1;i <= cnt;++ i) {
	    if((p[i].val - 1) % mod == 0) {
	        (ans *= (p[i].num * b + 1) % mod) %= mod;
	        continue ;
        }
        ull x = Power(p[i].val , b * p[i].num + 1);
        x = (x - 1 + mod) % mod;
        ull y = Power(p[i].val - 1 , mod - 2);
        (ans *= x * y % mod) %= mod;
	}                            
	printf("%lld",ans % mod);
	fclose(stdin);
	fclose(stdout);
	return 0;
}