題目描述

給定正整數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);}