#Poj1845#幂的约数之和

题目描述

给定正整数A, B，求A^B的所有因数之和，并模9901。

输入

仅一行，有两个整数A和B(0 <= A,B <= 50000000)

输出

第1行：问题的答案

样例输入

Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)

2 3
样例输出
15
提示
2^3 = 8
8 的约数是1， 2， 4， 8，相加得到15
对于一个大于1正整数n可以分解质因数：n=p1^a1*p2^a2*p3^a3*…*pk^ak,则由约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个，那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）证明：若n可以分解质因数：n=p1^a1*p2^a2*p3^a3*…*pk^ak,可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1... ...同理可知，pk^ak的约数有:pk^0, pk^1, pk^2......pk^ak ；实际上n的约数是在p1^a1、p2^a2、...、pk^ak每一个的约数中分别挑一个相乘得来，可知共有(a₁+1)(a₂+1)(a₃+1)…(ak+1)种挑法，即约数的个数。它们的和为：f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）本题将A分解质因数，并记录每种质因数的总个数，乘B，即A^B中共有该种质因数的个数，再利用约数和公式计算。值得注意的是，本题对结果取模9901，而等比数列前n项和公式中涉及除法运算，故不能在快速幂中取模，那么long long会溢出，所以此处采用二分法求等差数列前n项和。(notes for more information)
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const int mod=9901;int A,B;long long ans=1;long long qmul(long long p,long long k){	long long s=1,tmp=p;	while(k){		if(k%2)			s=s*tmp%mod;		tmp=tmp*tmp%mod;		k>>=1;	}	return s;}long long get_sum(long long p,long long k){//二分求解等比数列	if(!p)return 0LL;	if(!k)return 1LL;	if(k&1)		return ((1+qmul(p,k/2+1))%mod*get_sum(p,k/2)%mod)%mod;	return ((1+qmul(p,k/2+1))%mod*get_sum(p,k/2-1)+qmul(p,k/2)%mod)%mod;}void get_PR(int num){	int i;	long long prnow=0LL,now=0LL;	for(i=2; i<=num; ++i,now=0LL){		while(num%i==0)			num/=i,++now;		now*=B;		prnow=get_sum(i,now);		ans=ans*(prnow%mod)%mod;	}	return ;}int main(){	scanf("%d%d",&A,&B);	get_pr(A);	printf("%I64d/n",ans);}