记录编号	553405	评测结果	AAAAAAAAAAAAA
题目名称	[POJ 1845] Sumdiv	最终得分	100
用户昵称	Oasiz	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-08-19 15:54:46	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
ll a,b,ans;
struct num{
	int ba;
	int ex;
}d[100002];
ll pw(ll pn,ll pm){
    ll sq = 1;
    while(pm>0){
        if(pm%2){
            sq = (sq*pn)%9901;
        }
        pm = pm / 2;
        pn = pn * pn % 9901;
    }
    return sq;
}
ll g(ll pn,ll pm){
    if(pm == 0){
        return 1;
    }
    if(pm%2){
        return (g(pn,pm/2)*(1+pw(pn,pm/2+1)))%9901;
    }
    else{
        return (g(pn,pm/2-1)*(1+pw(pn,pm/2+1))+pw(pn,pm/2))%9901;
    }
}
int main(int argc, char** argv){
	freopen("sumdiv.in","r",stdin);
	freopen("sumdiv.out","w",stdout);
	cin>>a>>b;
	if(a==0){
		ans=0;
	}
	else{
		ans=1;
		int k=0;
        for(int i=2;i*i<=a;){
            if(a%i==0){
                d[k].ba=i;
                d[k].ex=0;
                while(a%i == 0)
                {
                    d[k].ex++;
                    a/=i;
                }
                k++;
            }
            if(i==2){
                i++;
            }
            else{
                i+=2;
            }
        }
        if(a!=1){
            d[k].ba=a;
            d[k].ex=1;
            k++;
        }
		for(int i=0;i<k;i++){       
            ans=(ans*(g(d[i].ba,d[i].ex*b)%9901)%9901);
        }
	}
	cout<<ans;
	return 0;
}