【题解】POJ1845 Sumdiv（乘法逆元+约数和）

POJ1845：http://poj.org/problem?id=1845

思路：

A^B可以表示成多个质数的幂相乘的形式：A^B=（a₁ⁿ¹）*(a₂ⁿ²)* ...*(a_m^nm)

根据算数基本定理可以得约数之和sum=(1+a₁+a_1²+...+a_1ⁿ¹)*(1+a₂+a_2²+...+a_2ⁿ²)*...*(1+a_m+a_m²+...+a_m^nm) mod 9901

对于每个(1+a_i+a_i²+...+a_iⁿⁱ) mod 9901=（a_i^_(ni+1)-1)/(a_i-1) mod 9901 （等比数列前n项目和）分母可用快速幂算出

因为9901是质数，只要a_i-1不是9901的倍数就只要计算a_i-1的乘法逆元inv（用费马小定理），再乘（a_i^_(ni+1)-1) 直接算出ans

PS：若a_i-1是9901的倍数此时乘法逆元不存在但是a_imod 9901=1 所以1+a_i+a_i²+...+a_iⁿⁱ=1+1+...+1=n_i+1

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

using namespace std;

#define mod 9901

int a,b,m,ans=;

int p[],c[];//p是质数 c是指数

void divide(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 quickpow(int a,long long b)

{

    int c=;

    for(;b;b>>=)

    {

        if(b&)

        c=(long long)c*a%mod;

        a=(long long)a*a%mod;

    }

    return c;

}

int main()

{

    cin>>a>>b;

    divide(a);//分解A的质因数 b到后面在乘上

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

    {

        if((p[i]-)%mod==)//特判当ai-1是9901的倍数 乘法逆元不存在

        {

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

            continue;

        }

        int x=quickpow(p[i],(long long)b*c[i]+);//快速幂求分母

        x=(x-+mod)%mod;

        int y=p[i]-;

        y=quickpow(y,mod-);//根据费马小定理求乘法逆元

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

    }

    cout<<ans;

}

巴特西

【题解】POJ1845 Sumdiv（乘法逆元+约数和）

思路：

代码：

最新文章

热门文章