POJ 1845 Sumdiv [素数分解快速幂取模二分求和等比数列]

大致题意：

求A^B的所有约数（即因子）之和，并对其取模 9901再输出。

解题基础：

1） 整数的唯一分解定理：

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

$A= p_1^{k_1}*p_2^{k_2}*p_3^{k_3}...p_n^{k_n}$ ，其中 $p_i$ 为素数

2） 约数和公式：

对于已经分解的整数 $A= p_1^{k_1}*p_2^{k_2}*p_3^{k_3}...p_n^{k_n}$ ，A的所有因子之和为 $S=(1+p_1+p_1^{2}+p_1^{3}+...+p_1^{k_1})*(1+p_2+p_2^{2}+p_2^{3}+...+p_2^{k_2})*...*(1+p_n+p_n^{1}+p_n^{2}+p_n^{3}+...+p_n^{k_n})$

3） 同余模公式：

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m*b%m)%m

1: 对A进行素因子分解

这里如果先进行筛50000内的素数会爆空间，只能用最朴素的方法进行分解

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

$Sum=(1+p_1+p_1^{2}+p_1^{3}+...+p_1^{a_1*B})*(1+p_2+p_2^{2}+p_2^{3}+...+p_2^{k_2*B})*...*(1+p_n+p_n^{1}+p_n^{2}+p_n^{3}+...+p_n^{k_n*B})$

3: 求2中的等比序列

由于给的数据量大，肯定不能直接用等比序列的求和公式，要用分治法进行求解

$S_n=1+q_1+q_2+q_3+...+q_n$ $\rightarrow$ $S_2n=(1+q_1+q_2+...q_n)+(1+q_1+q_2+...+q_n)*q_n=(1+q_1+q_2+..+q_n)*(1+q_n)=Sn*(1+q_n)$

一直对 $S_n$ 递归求解

S的下标为偶数类比一下

4：反复平方法计算幂次式 $p^{n}$

一个快速幂取模的板子，直接套上

#include<iostream>

#include<string.h>

#include<cstdio>

using namespace std;

int p[10000];

int q[10000];

const int mod = 9901;

//快速幂取模板子

long long qucick_pow(int m, int n, int moD)

{

    if(n == 0)

        return 1;

    long long x = qucick_pow(m, n / 2, moD);

    long long ans = x * x % mod;

    if(n % 2)

        ans = ans * m % mod;

    return ans;

}

// 递归求解等比数列

long long sum(int m, int n)

{

    if(n == 0)

        return 1;

    if(n % 2)

    {

        return (sum(m, n / 2) * (1 + qucick_pow(m, n / 2 + 1, mod))) % mod;

    }

    else

    {

        return (sum(m, n / 2 - 1) * (1 + qucick_pow(m, n / 2 + 1, mod)) + qucick_pow(m, n / 2, mod)) % mod;

    }

}

int main()

{

    int a, b;

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

    int cnt = 0;

    for(int i=2;i*i<=a;)

    {

        if(a%i==0)

        {

            p[cnt]=i;

            while(a%i==0)

            {

                a/=i;

                q[cnt]++;

            }

            cnt++;

        }

        if(i==2)

            i+=1;

        else

            i+=2;

    }

    if(a!=1)

        p[cnt]=a,q[cnt++]=1;

    long long ans = 1;

    for(int i = 0; i < cnt; i++)

    {

        ans = (ans * (sum(p[i], q[i] * b) % mod)) % mod;

    }

    cout << ans % mod << endl;

}

巴特西

POJ 1845 Sumdiv [素数分解快速幂取模二分求和等比数列]

最新文章

热门文章

巴特西

POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

最新文章

热门文章

POJ 1845 Sumdiv [素数分解快速幂取模二分求和等比数列]