解题报告 P1593 因子和

题意

求 a^b 的正约数和模 9901 的值。

思路

考虑对 a 进行质因数分解，得到

a=\prod p_i^{c_i}

易知 a^b=\prod p_i^{bc_i}

其所有约数和即为

\prod\sum_{k=0}^{bc_i}p_i

注意到其为一个等比数列，所以我们可以将其化为

\prod\dfrac{p_i^{bc_i+1}-1}{p_i-1}

最终就是求出 (\prod (p_i^{bc_i+1}-1))\bmod 9901，然后求出所有 p_i-1 的逆元即可。

但问题是，如果 p_i-1\equiv0\pmod{9901}，即 p_i\bmod9901=1，则 p_i-1 不存在逆元，然而等比数列还是有意义的，所以需要进行特判：

具体地，这段数列即为 1+p_i\bmod9901+p_i^2\bmod 9901+\cdots+p_i^{c_i}\bmod9901\equiv1+c_i\pmod{9901}。特判即可。

#include <cstdio>
#include <vector>

const int mod=9901,maxn=5e7+10;

int pow(int base,int p)
{
    int ret=1;
    base%=mod;
    for(;p;p>>=1)
    {
        if(p&1)
            ret=ret*base%mod;
        base=base*base%mod;
    }
    return ret;
}

int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    if(b==0)
    {
        printf("1\n");
        return 0;
    }
    int ans=1,cnt=0;
    for(int i=2;i*i<=a;++i)
    {
        int t=0;//t记录i的次数
        if((!(a%i))&&a!=1)
        {
            do
            {
                t++;
                a/=i;
            }while((!(a%i))&&a!=1);
        }
        t*=b;
        if(i%mod==1)//上文的特判
            ans=ans*(t+1)%mod;
        else
        {
            ans=ans*(pow(i,t+1)+mod-1)%mod;
            ans=ans*(pow(i-1,mod-2)+mod)%mod;
        }
        if(a==1)break;
    }
    if(a!=1)//如果还有一个比较大的因子
    {
        if(a%mod==1)
            ans=ans*(b+1)%mod;
        else
        {
            ans=ans*(pow(a,b+1)+mod-1)%mod;
            ans=ans*(pow(a-1,mod-2)+mod)%mod;
        }
    }
    printf("%d\n",ans%mod);
    return 0;
}