【POJ1845】Sumdiv【算数基本定理 + 逆元】

描述

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

输入

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

输出

The only line of the output will contain S modulo 9901.

样例输入

2 3

样例输出

15

提示

2^3 = 8.

The natural divisors of 8 are: 1,2,4,8. Their sum is 15.

15 modulo 9901 is 15 (that should be output).

大概意思是让我们求 \(a^b\) 的所有因数的和膜9901的值

我们知道在算数基本定理中有 : \(a=p_{1}^{c_{1}}*p_{2}^{c_{2}}........*p_{n}^{c_{n}}\)(第一次用LaTeX)

所以\(a^b\)的约数和为 \((1+p_{1}+p_{1}^{2}.......+p_{1}^{b*c_{1}})*(1+p_{2}+p_{2}^{2}.......+p_{2}^{b*c_{2}}).....*(1+p_{n}+p_{n}^{2}.......+p_{n}^{b*c_{n}})\)

对于上面的每一项我们用等比公式求和

\(1+p_{1}+p_{1}^{2}.......+p_{1}^{b*c_{1}}\) = \(p_{1}^{b*c_{1}+1}-1\)/\(p_{1}-1\)

#include <cstdio>

#include <vector>

typedef long long int ll;

const ll mod=9901;

std::vector<ll> prime;

std::vector<ll> times;

inline void divide(ll n) {

    for(ll i=2;i*i<=n;++i) {

        if(n%i==0) {

            prime.push_back(i);ll cnt=0;

            while(n%i==0) {n/=i;++cnt;}

            times.push_back(cnt);

        }

    }

    if(n>1) {prime.push_back(n);times.push_back(1);}

}

inline ll qpow(ll n,ll k) {

    ll ans=1;

    while(k) {

        if(k&1) ans=ans*n%mod;

        n=n*n%mod;k>>=1;

    }

    return ans;

}

int main() {

    ll a,b;scanf("%lld%lld",&a,&b);

    divide(a);

    ll ans=1;

    for(int i=0,end=prime.size();i<end;++i) {

        times[i]*=b;

        if((prime[i]-1)%mod==0) ans=ans*(times[i]+1)%mod;

        else ans=ans*((qpow(prime[i],times[i]+1)-1+mod)*qpow(prime[i]-1,mod-2)%mod)%mod;

    }

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

    return 0;

}

巴特西

【POJ1845】Sumdiv【算数基本定理 + 逆元】

最新文章

热门文章