洛谷 P1593 因子和

https://www.luogu.org/problemnew/show/P1593#sub

利用约数和定理：可以去看一下公式第13条

然后这个题目的话，要求$a^b$，那么我们首先可以先将a分解然后给指数乘上$b$.

然后我们就需要计算$(1+p+p^2+....p^k)$因为k可能特别大，所以直接计算是不可能了。

看完公式后，我们当然可以利用等比公式计算了，然而还要求逆元，这题不用那么麻烦啦。

费马小定理可以解决这个问题：公式第14条

$$a^x \equiv a^{\mu(x)}mod p,\mu(x)=x-1 $$

因为模数比较小那么在我们计算的时候显然会有循环节的出现，那么我们只需要计算这个循环节就好了。

然后将每一个质因数的答案想乘就可以得到答案啦。

注意开$long long$

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

#define mod 9901

#define LL long long

LL a,b,x;

LL pri[],cnt[],ans,tot,pw[];

int main()

{

    cin>>a>>b;

    x=a;

    for(int i=;i*i<=a;i++)

    {

        if(x%i==)

        {

            pri[++tot]=i;

            while(x%i==)

            {

                cnt[tot]++;

                x/=i;

            }

        }

    }

    if(x!=)

    {

        pri[++tot]=x;

        cnt[tot]=;

    }

    ans=;

    for(int i=;i<=tot;i++)cnt[i]*=b;

    for(int i=tot;i>=;i--)

    {

        pw[]=;

        LL s=,as=;

        for(int j=;j<=&&j<=cnt[i];j++)

        {

            pw[j]=pw[j-]*pri[i]%mod;

            (s=s+pw[j])%=mod;

            if(cnt[i]%==j)as=s;

        }

        ans=(ans*((cnt[i]/)*s+as)%mod)%mod;

    }

    cout<<ans;

}

巴特西

洛谷 P1593 因子和

最新文章

热门文章