POJ 1845 Sumdiv （整数拆分+等比快速求和）

　　当我们拆分完数据以后，

　　A^B的所有约数之和为：

sum = [1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...*[1+pn+pn^2+...+pn^(an*B)].

　　当时面对等比数列的时候，想到了求和公式，因为直接算超时了，但是带膜除法不能直接除，所以又想到了乘法逆元，但是逆元的使用条件是除数和mod互质的时候，题目给我们的膜不够大，然后我就方了，不知道该怎么去处理了，后来看到网上，才学会了等比快速求和的方法。

　　它的思想是二分法+递归，规律如下：

（1）若n为奇数,一共有偶数项，则：
1 + p + p^2 + p^3 +...+ p^n

= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))
= (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

（2）若n为偶数,一共有奇数项,则:
1 + p + p^2 + p^3 +...+ p^n

= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)
= (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);

　至于幂的求法，可以用快速幂去求。代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

///sqrt(50000000) = 7071.07;///数据足够

/// num = a1(q^n - 1)/ (q-1);///方法难以使用

const long long Mod = ;

#define maxn 8000

#define LL long long

LL a,b,p[maxn],e[maxn],tot;

void split()

{

    int d = sqrt(a*1.0);///素数因子在它的根号之下

    tot = ;

    memset(e,,sizeof(e));

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

    {

        if(a == ) break;

        if(a%i == )

        {

            p[tot] = i;

            while(a % i == )

            {

                a /= i;

                e[tot]++;

            }

            tot++;

        }

        if(i == ) i--;///这种方法求素数很高效

    }

    if(a != )

    {

        p[tot] = a;

        e[tot]++;

        tot++;

    }

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

        e[i] *= b;

    /*for(int i = 0;i < tot;i++){

        printf("p[%d] = %lld   e[%d] = %lld\n",i,p[i],i,e[i]);

    }*/

}

LL mypow(LL a,LL b)

{

    if(b == ) return ;

    if(b == ) return a % Mod;

    if(b %  == ) return mypow(((a%Mod)*(a%Mod))%Mod,b/)%Mod;

    else return ((a%Mod) * mypow(a%Mod,b-)) % Mod;

}

LL get_sum(LL a,LL b)

{

    if(b==) return ;

    if(b % ) return ((get_sum(a,b/)%Mod)*(+mypow(a,b/+))%Mod) % Mod;

    else return ((get_sum(a,b/-)%Mod * (+mypow(a,b/+)%Mod))%Mod + mypow(a,b/)%Mod) % Mod;

}

int main()

{

    while(~scanf("%I64d %I64d",&a,&b))

    {

        split();

        LL ans = ;

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

        {

            ans = ans * get_sum(p[i],e[i])%Mod;///这里不可以省略

        }

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

    }

    return ;

}

　注意：这里有一个很难发现的错误，在取膜的时候不可以使用 ans ×= 的形式，优先级的不同会让他溢出。

巴特西

POJ 1845 Sumdiv （整数拆分+等比快速求和）

最新文章

热门文章