这道题主要思想是分治 $+$ 快速幂。
首先假设 $A={a_1}^{c_1}\times {a_2}^{c_2}\times {a_3}^{c_3}\times…\times {a_m}^{c_m}.$ 其中 $a_1\le a_2\le a_3…\le a_m$ ,且 $a_1,a_2,…a_m$ 均为素数,并且 $c_1,c_2,…,c_m≥1.$ 所以 $A^B={a_1}^{c_1\times B}\times {a_2}^{c_2\times B}\times {a_3}^{c_3\times B}\times…\times {a_m}^{c_m\times B}。$
根据乘法分配律,那么 $A^B$ 的约数和就是:$(1+a_1+{a_1}^2+…+{a_1}^{c_1\times B})\times (1+a_2+{a_2}^2+…+{a_2}^{c_2\times B})\times…\times (1+a_m+{a_m}^2+…+{a_m}^{c_m\times B}).$
我们发现每个乘项都是结构相同的,所以我们接下来以计算 $(1+a_1+{a_1}^2+…+{a_1}^{c_1\times B})$ 为例。
我们定义 $\text{add(x,y)}$ 代表 $(1+x+x^2+…+x^y)\text{ mod 9901}$ 的值,不难发现 $(1+a_1+{a_1}^2+…+{a_1}^{c_1\times B})=\text{add(}a_1,c_1\times \text{B).}$
我们可以写下以下的程序:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B;
#define MOD 9901
void depart(ll a,ll b){
if(a==0){
cout<<0<<endl;
exit(0);
}//特判 0^b
if(a==1){
cout<<1<<endl;
exit(0);
}//特判 1^b
ll ans=1; ll c=a; ll j=2;
while(c){
ll ui=0;
while(c%j==0) ui++,c/=j;
if(ui) {
ans*=add(j,b*ui); ans%=MOD;
}
j++; if(c==1) break;
}
cout<<ans<<endl;
}
int main(){
cin>>A>>B;
depart(A,B);
return 0;
}
接下来推导 $\text{add(x,y)}$ 的求法。
如果使用等比数列求解,那么因为要进行除法,不易进行取模。
我们可以使用分治法求解。
$(1). y\% 2==1:$
$\text{add(x,y)}=1+x+x^2+…+x^y$
$\text{add(x,y)}=1+x+x^2+…+x^{(y-1)/2}+x^{(y+1)/2}+…+x^y$
$\text{add(x,y)}=1+x+x^2+…+x^{(y-1)/2}+x^{(y+1)/2}\times(1+x+x^2+…+x^{(y-1)/2})$
$\text{add(x,y)}=(1+x+x^2+…+x^{(y-1)/2})\times(1+x^{(y+1)/2})$
$\text{add(x,y)}=\text{add(x,(y-1)/2)}\times(1+x^{(y+1)/2})$
对于 $x^{(y+1)/2}$,我们可以采用快速幂进行求解,这里只给出代码,就不讲解了。如果不太了解,可以参见 这道题目 进行练习。
ll QuickPow(ll p,ll c){
ll ans=1;
for(;c;c>>=1){
if(c&1) ans=(ll)ans*p%MOD;
p=(ll)p*p%MOD;
}
return ans;
}
同理,当 $y \% 2==0:$
$\text{add(x,y)}=1+x+x^2+…+x^y$
$\text{add(x,y)}=1+x+x^2+…+x^{y/2-1}+x^{y/2}+x^{y/2+1}+…+x^y$
$\text{add(x,y)}=1+x+x^2+…+x^{y/2-1}+x^{y/2}\times(1+x+x^2+…+x^{y/2-1})+x^y$
$\text{add(x,y)}=(1+x+x^2+…+x^{y/2-1})\times(1+x^{y/2})+x^y$
$\text{add(x,y)}=\text{add(x,y/2-1)}\times(1+x^{y/2})+x^y$
用分治 $+$ 快速幂即可。
注意边界问题:当 $x=0,\text{add(x,y)}=0;x=1,\text{add(x,y)}=1.$
总代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B;
#define MOD 9901
ll QuickPow(ll p,ll c){
ll ans=1;
for(;c;c>>=1){
if(c&1) ans=(ll)ans*p%MOD;
p=(ll)p*p%MOD;
}
return ans;
}
ll add(ll p,ll c){
if(c==0) return 1;
if(c==1) return (1+p)%MOD;
if(c&1){
return ((1+QuickPow(p,(c+1)>>1))%MOD*add(p,(c-1)>>1)%MOD)%MOD;
}
else{
return (((1+QuickPow(p,c>>1))%MOD*add(p,c/2-1)%MOD)+QuickPow(p,c))%MOD;
}
}
void depart(ll a,ll b){
if(a==0){
cout<<0<<endl;
exit(0);
}
if(a==1){
cout<<1<<endl;
exit(0);
}
ll ans=1;
ll c=a;
ll j=2;
while(c){
ll ui=0;
while(c%j==0) ui++,c/=j;
if(ui) {
ans*=add(j,b*ui);
ans%=MOD;
}
j++;
if(c==1) break;
}
cout<<ans<<endl;
}
void file(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
}
int main(){
// file();
cin>>A>>B;
depart(A,B);
return 0;
}