[POJ]P1845 Sumdiv
原题链接：P1845 Sumdiv
题意
给定$A,B$，求$A^B$对9901取模的值。
分析
先说说我的第一思路：模数是很小的，完全可以开一个桶放下所有的幂次方。
所以我们可以把每个数分解质因数了，然后把每个质数的所有幂次方装进桶里。
然后我们从$1$到$9901$枚举每一位，同时统计他们的个数积，最后答案加上(个数积$ imes$幂次方积)就可以了。。
发现时间有点爆炸。。。
而且这些所谓的优化好像是用处不大的。。
考虑从数论的层面上解决？？
首先$$A^B=p_1^{Ba_1} imes p_2^{Ba_2} imes cdots imes p_m^{Ba_m}$$
那么所有的质因数的和就是枚举每一位指数
我们先提取含$p_1$的式子
$$sum_{k_1,k_2,cdots ,k_m}^{k_1leq Ba_1,k_2leq Ba_2,cdots ,k_mleq Ba_m}{({p_1}^{k_1}+{p_2}^{k_2}+cdots +{p_m}^{k_m})(cdots)}$$
然后我们把后面的也化简之后，每个因数就剩下它的等比数列求和了，我们利用求和公式
最后答案就是$$sum_{i=1}^m{frac{p_i^{Ba_i+1}-1}{p_i-1}}$$
我们对每一个$p_i-1$求一下逆元就ok了。
但是这道题真的这么简单吗。。。
逆元通常求法是费马小定理或是exgcd，这些都要求模数与求的数互质。。
这道题显然不一定互质。。
怎么办呢？
$x=frac{a}{b} mod{p}=frac{amod pb}{b}$
这样就可以了（写了一上午心态爆炸）。。
代码
1 #include <iostream> 2 #include <cstring> 3 #include <set> 4 #include <algorithm> 5 #include <cstdio> 6 #include <cmath> 7 #define ll long long 8 #define ull unsigned long long 9 #define Mid ((l+r)<<1) 10 using namespace std; 11 const int N=2e7+1009; 12 const ll mod=9901; 13 ll read(){ 14 char c;ll num,f=1; 15 while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0'; 16 while(c=getchar(), isdigit(c))num=num*10+c-'0'; 17 return f*num; 18 } 19 ll a,b,ans=1; 20 ll ksc(ll x,ll y,ll md){ 21 return (x*y-(ll)((long double)x/md*y)*md+md)%md; 22 } 23 ll Pow(ll a,ll p,ll md){ 24 ll ans=1; 25 for(;p;p>>=1,a=ksc(a,a,md)) 26 if(p&1)ans=ksc(a,ans,md); 27 return ans; 28 } 29 int main() 30 { 31 //cout<<ksc(111,111)<<endl; 32 a=read();b=read(); 33 if(a==0){ 34 printf("0 "); 35 return 0; 36 } 37 for(int i=2;i<=sqrt(a);i++){ 38 if(a%i)continue; 39 int num=0; 40 while(a%i==0)num++,a/=i; 41 ans=ksc(ans,(Pow(i,num*b+1,mod*(i-1))+(mod*(i-1))-1)/(i-1),mod); 42 } 43 if(a>1) 44 ans=ksc(ans,(Pow(a,b+1,mod*(a-1))+(mod*(a-1))-1)/(a-1),mod); 45 printf("%lld ",ans); 46 return 0; 47 }