2018.09.11 poj1845Sumdiv（质因数分解+二分求数列和）

传送门

显然需要先求出ab" role="presentation" style="position: relative;">abab的所有质因数和它们的指数。

但求出来之后并不能直接上等比数列求和公式。

因为这道题并不能直接求逆元。

原因？

a的某个因数有可能已经大于9901了。

于是它可能是9901的倍数。

这样就gg了。

于是我们可以二分求解等比数列的和。

代码：

#include<iostream>#include<cmath>#define mod 9901#define ll long long#define xx first#define yy secondusing namespace std;int a,b,tot=0;ll ans=1;inline ll ksm(ll x,ll p){ ll ret=1; while(p){ if(p&1)ret=ret*x%mod; x=x*x%mod,p>>=1; } return ret;}inline ll calc(ll x,ll y){ if(!y)return 1; if(y&1)return ((1+ksm(x,y/2+1))*calc(x,y/2))%mod; return ((1+ksm(x,y/2+1))*calc(x,y/2-1)+ksm(x,y/2))%mod;}int main(){ cin>>a>>b; for(int i=2;i*i<=a;++i){ int cnt=0; while(a%i==0)a/=i,++cnt; (ans*=calc(i,cnt*b))%=mod; } if(a-1)(ans*=calc(a,b))%=mod; cout<<ans; return 0;}