题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// //求约数之和是有公式的
// A=p1^k1*p2^k2....*pn^kn
// (k1+1)*(k2+1).....*(kn+1)总共有这么多选法 
// (p0^0+p0^1...p0^n)*(p1^0+p1^1...p1^n)*....*(pn^0+pn^1...pn^n)//这是所有的约数之和
// sum(p,k)=p^0+p^1+.....p^k=(p^0+....p^(k/2))+(p^(k/2+1)+....+p^k)=(1+p^(k/2+1))sum(p,k/2) 如果是偶数项数可以分成两半
// 如果是奇数项  
// A^B=p1^k1B  * p2^k2B.....*  pn^knB 
#include<iostream>
using namespace std;
const int mod =9901;
int qim(int a,int k){
    a%=mod;//先将
    int res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

long long sum(int p,int k){
    if(k==0){
        return 1;
    }else if(k%2==0){
        return (1+p%mod*sum(p,k-1))%mod;
    }else{
        return(1+qim(p,k/2+1))*sum(p,k/2)%mod;
    }
}
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;//求当前的幂次
        }
        res=res*sum(i,s*b)%mod;
    }
    if(a==0){
        res=0;
    }
    cout<<res<<endl;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla