POJ 1845 Sumdiv（求因数和 + 逆元）题解

题意：给你a，b，要求给出a^b的因子和取模9901的结果。

思路：求因子和的方法：任意A = p1^a1 * p2^a2 ....pn^an，则因子和为sum =（1 + p1 + p1^2 + ... . + p1^a1）*（1 + p2 + p2^2 + ... . + p2^a2）*（1 + pn + pn^2 + .... + pn^an）。又由等比数列求和公式可知 1 + pn + pn^2 + .... + pn^an =（pn^an - 1）/（pn - 1）。因为要mod 9901，所以除数取模要用到逆元：A / B mod m = （A mod（B * m））/ B。在快速幂求解过程中会爆过程，所以手动写了乘法。

参考：逆元详解【逆元】

补充：

任意A = p1^a1 * p2^a2 ....pn^an

因数和：sum =（1 + p1 + p1^2 + ... . + p1^a1）*（1 + p2 + p2^2 + ... . + p2^a2）*（1 + pn + pn^2 + ... . + pn^an）

因数个数：num = （a1 + 1）*（a2 + 1）....（an + 1）

代码：

#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn =  + ;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

ll mul(ll a, ll b, ll c){

    ll ans = ;

    while(b){

        if(b & ){

            ans = ans + a;

            if(ans > c) ans -= c;

        }

        a = a + a;

        if(a > c) a -= c;

        b >>= ;

    }

    return ans;

}

ll pmul(ll a, ll b, ll c){

    a = a % c;

    ll ans = ;

    while(b){

        if(b & ) ans = mul(ans, a, c);

        a = mul(a, a, c);

        b >>= ;

    }

    return ans;

}

int main(){

    ll a, b;

    while(~scanf("%lld%lld", &a, &b)){

        ll ans = ;

        for(ll i = ; i * i <= a; i++){

            if(a % i == ){

                ll num = ;

                while(a % i == ){

                    a /= i;

                    num++;

                }

                ans *= (pmul(i, b * num + , (i - ) * MOD) - ) / (i - );

                ans %= MOD;

            }

        }

        if(a > ){

            ans *= (pmul(a, b + , (a - ) * MOD) - ) / (a - );

            ans %= MOD;

        }

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

    }

    return ;

}

巴特西

POJ 1845 Sumdiv（求因数和 + 逆元）题解

最新文章

热门文章