C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 428K, 提交时间: 2022-08-14 19:30:13

#include<bits/stdc++.h>
using namespace std;
const int m=9901;   //取模数
int ksm(int x,int y) {
	int t=1;
	while(y) {
		if(y&1)
			t=t*x%m;
		x=x*x%m;
		y>>=1;
	}
	return t;
}
int sum(int p,int k) {
	if(k==0) return 1;
	if(k%2==0) return (p%m*sum(p,k-1)+1)%m;
	return (1+ksm(p%m,k/2+1))*sum(p,k/2)%m;
}
int main() {
	int a,b;
	cin>>a>>b;
	int res=1;
	for(int i=2; i<=a; i++) {
		int s=0;
		while(a%i==0) {
			s++;
			a/=i;
		}
		if(s) res=res*sum(i,s*b)%m;
	}
	if(a==0) res=0;
	cout<<res<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-08-05 14:13:27

#include<cstdio>
using namespace std;
#define ll long long
const int p=9901;
inline int pow(int x,int y){
	int ret=1%p;
	for(;y;y>>=1,x=(ll)x*x%p)
	 if (y&1) ret=(ll)ret*x%p;
	return ret;
}

int main(){
	int a,b,ans=1;
	scanf("%d%d",&a,&b);
	if (!a) return puts("0")&0;
	for (int i=2,num;i*i<=a;i++){
		num=0;
		while(a%i==0) a/=i,num++;
		if (num) ans=ans*(pow(i,num*b+1)-1+p)%p*pow(i-1,p-2)%p;		
	}
	if (a>1) ans=ans*(pow(a,b+1)-1+p)%p*pow(a-1,p-2)%p; 
	printf("%d",ans);
}

C++ 解法, 执行用时: 3ms, 内存消耗: 404K, 提交时间: 2021-09-20 17:02:08

#include<cstdio>
using namespace std;
#define ll long long
const int p=9901;
inline int pow(int x,int y){
	int ret=1%p;
	for(;y;y>>=1,x=(ll)x*x%p)
	 if (y&1) ret=(ll)ret*x%p;
	return ret;
}

int main(){
	int a,b,ans=1;
	scanf("%d%d",&a,&b);
	if (!a) return puts("0")&0;
	for (int i=2,num;i*i<=a;i++){
		num=0;
		while(a%i==0) a/=i,num++;
		if (num) ans=ans*(pow(i,num*b+1)-1+p)%p*pow(i-1,p-2)%p;		
	}
	if (a>1) ans=ans*(pow(a,b+1)-1+p)%p*pow(a-1,p-2)%p; 
	printf("%d",ans);
}