C++(g++ 7.5.0) 解法, 执行用时: 603ms, 内存消耗: 468K, 提交时间: 2023-01-17 17:41:56

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 9901
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll sum( ll p, ll c)
{
    if(c==0)
    return 1;
    if(c&1)
    return ((1+ksm(p,(c+1)/2))*sum(p,(c-1)/2))%mod ;
    else
    return ((1+ksm(p,c/2))*sum(p,c/2-1)+ksm(p,c))%mod;
}
int main()
{
    ll a,b;
    ll ans=1;
    cin>>a>>b;
    for(ll i=2;i<=a;i++)
    {
        ll s=0;
        while(a%i==0)
        {
            s++;
            a/=i;
         } 
         ans=ans*sum(i,s*b)%mod;
    }
    if(a==0)
    cout<<"0"<<endl;
    else
    cout<<ans<<endl;
    return 0;
}
 

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 612K, 提交时间: 2020-10-10 15:05:28

#include<cstdio>
using namespace std;
const int mod=9901;
int a,b,ans=1;
int power(int a,int b){
	a%=mod;
	int prod=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)prod=prod*a%mod;
	return prod;
}void up(int p,int r){
	if(p%9901==1)ans=(b*r+1)%mod*ans%mod;
	else ans=ans*(power(p,b*r+1)-1)%mod*power(p-1,mod-2)%mod;
}int main(){
	scanf("%d%d",&a,&b);
	for(int i=2,r;i<=a/i;i++){
		for(r=0;!(a%i);r++)a/=i;
		up(i,r);
	}if(a!=1)up(a,1);
	printf("%d",ans),putchar('\n');
	return 0;
}