Sumdiv

题意：求a^b的所有约数之和mod9901。

思路：因为一个数A能够表示成多个素数的幂相乘的形式。即A=(a1^n1)*(a2^n2)*(a3^n3)...(am^nm)。所以这个题就是要求

(1+a1+a1^2+...a1^n1)*(1+a2+a2^2+...a2^n2)*(1+a3+a3^2+...a3^n2)*...(1+am+am^2+...am^nm) mod 9901。

对于每一个(1+a1+a1^2+...a1^n1) mod 9901

等于 (a1^(n1+1)-1)/(a1-1) mod 9901，这里用到逆元的知识：a/b mod c = (a mod (b*c))/ b

所以就等于(a1^(n1+1)-1)mod (9901*(a1-1)) / (a1-1)。

至于前面的a1^(n1+1)，快速幂。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<cmath>

#define ll long long

using namespace std;

int a,b,m,ans=,mod=;

int p[],c[];

void devide(int n)

{

    m=;

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

    {

        if(n%i==)

        {

            p[++m]=i;

            c[m]=;

            while(n%i==)

            {

                n/=i;

                c[m]++;

            }

        }

    }

    if(n>)

    p[++m]=n,c[m]=;

}

int power(int a,ll b)

{

    int c=;

    for(;b;b>>=)

    {

        if(b&)

        c=(ll)c*a%mod;

        a=(ll)a*a%mod;

    }

    return c;

}

int main()

{

    scanf("%d%d",&a,&b);

    devide(a);

    for(int i=;i<=m;i++)

    {

        if((p[i]-)%mod==)

        {

            ans=((ll)b*c[i]+)%mod*ans%mod;

            continue;

        }

        int x=pow(p[i],(ll)b*c[i]+);

        x=(x-+mod)%mod;

        int y=p[i]-;

        y=power(y,mod-);

        ans=(ll)ans*x%mod*y%mod;

    }

    printf("%d\n",ans);

}

巴特西

Sumdiv

最新文章

热门文章