这还是一道综合了许多数论的知识点的，做完也涨了不少姿势
但还是因为约数和公式这个鬼东西去找了度娘
题意很简单，就是求\(A^B\)的约数之和\(mod\ 9901\)。
但是这种题意越是简单的题目越是坑人
首先如果你不知道约数和公式就绝逼GG，然后由于有唯一分解定理这种东西撑腰，我们选择直接用公式.
先分解质因数得到\(n\)个质因数\(p_i\)和它们出现的次数\(t_i\)，然后约数和：
\(\prod_{i=1}^{n} \sum_{j=0}^{t[i]} {p_i}^j\)
然后我们考虑如何处理那个\(\sum_{j=0}^{t} {p}^j\)
首先我们可以发现这是一个等比数列，然后我们来对它进行转化，我们设\(S=\sum_{j=0}^{t} {p}^j ......(1)\)，则有
\(pS=\sum_{j=1}^{t+1} {p}^j ......(2)\)
我们\((2)-(1)\)得
\((p-1)S=p^{t+1}-1\)
即
\(S=\frac{p^{t+1}-1}{p-1}\)
所以我们上面用快速幂，下面用逆元即可，然后就解决了
但其实这道题的坑点让人难以想象：
- 当\(9901\mid p-1\)时不能用逆元，要特殊处理
- 因为这道题的次数不能取模，所以要涉及到两个long long的数相乘，但是由于取模所以不用高精，所以我们用二进制的方法（其实就是和快速幂一样的思想）来做快速乘
- 分解质因数的时候这个数可能本身就是质数（这个比较经典）
然后我们就可以艹过去了
CODE
#include<cstdio>
using namespace std;
typedef long long LL;
const LL S_N=10005,mod=9901;
LL a,b,prime[S_N],t[S_N],ex,cnt,ans=1;
bool vis[S_N];
inline void Euler(LL m)
{
register LL i,j; vis[1]=1;
for (i=2;i<m;++i)
{
if (!vis[i]) prime[++cnt]=i;
for (j=1;j<=cnt&&i*prime[j]<m;++j)
{
vis[i*prime[j]]=1;
if (!(i%prime[j])) break;
}
}
}
inline void resolve(LL x)
{
register LL i;
for (i=1;i<=cnt;++i)
{
while (!(x%prime[i])) x/=prime[i],++t[i];
if (!(x^1)) break;
}
if (x^1) ex=x;
}
inline LL quick_mul(LL x,LL y,LL mod)
{
LL tot=0;
while (y)
{
if (y&1) tot=(tot+x)%mod;
x=(x<<1)%mod; y>>=1;
}
return tot;
}
inline LL quick_pow(LL x,LL p,LL mod)
{
LL tot=1;
while (p)
{
if (p&1) tot=quick_mul(tot,x,mod);
x=quick_mul(x,x,mod); p>>=1;
}
return tot;
}
inline LL inv(LL x)
{
return quick_pow(x,mod-2,mod);
}
inline LL calc(LL p,LL t)
{
return (((quick_pow(p,t,mod)-1+mod)%mod)*inv(p-1))%mod;
}
int main()
{
Euler(S_N); scanf("%lld%lld",&a,&b); resolve(a);
for (register LL i=1;i<=cnt;++i)
if (t[i])
{
if ((prime[i]-1)%mod) ans=(ans*calc(prime[i],t[i]*b+1))%mod;
else ans=(ans*quick_pow(prime[i],t[i]*b+1,mod*(prime[i]-1))/(prime[i]-1))%mod;
}
if (ex)
{
if ((ex-1)%mod) ans=(ans*calc(ex,b+1))%mod;
else ans=(ans*quick_pow(ex,b+1,mod*(ex-1))/(ex-1))%mod;
}
printf("%lld",ans);
return 0;
}