POJ 1845 Sumdiv 解题报告

时间：2010-05-25 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=1845

二、解题思路

这是道数论的题，需要用到的知识点有：

（1）素因子分解唯一性定理：任意正整数都能用一种方式且只有一种方式写出素数的乘积。

如: 60 =2^2*3*5

（2）约数和公式: 将A^B 分解成素因数形式：

A^B=(p1^k1)*(p2^k2)*(p3^k3)………

那么A^B所有因子之和就是

S=(1+p1+p1^2+p1^3+…..p1^k1)*(1+p2+p2^2+p2^3+…..p2^k2)*(1+p3+…)*…………..

最后计算a^b mod MOD和求约数和的时候用到了二分的思想。

参考了：http://hi.baidu.com/aconly/blog/item/1a25845d1bfbbc44fbf2c0bf.html

三、代码

#include<iostream>
using namespace std;
const int MOD=9901;
const int MAXN=9901;
int prim[MAXN],cnt;
bool b[MAXN];
//获取质数表
void GetPrim()
{
    int i,j;
    cnt=0;
    for(i=2;i<MAXN;++i)
    {
        if(b[i]==0)
        {
            prim[cnt++]=i;
            for(j=i+i;j<MAXN;j+=i)
                prim[j]=1;
        }
    }
}
//计算 a^b mod MOD
__int64 Exp(__int64 a,__int64 b)
{
    if(1==b)
        return a;
    __int64 t=Exp(a,b/2);
    if(b&1)
        return (t*t*a)%MOD;
    return (t*t)%MOD;
}
//计算(1+p+p^2+...+p^k) mod MOD
__int64 Sum(__int64 p, __int64 k)
{
    if(1==k)
        return 1;
    __int64 t=Sum(p,k/2);
    if(k&1)
        return (t+Exp(p,k/2)*(1+p*t))%MOD;
    else
        return ((1+Exp(p,k/2))*t)%MOD;

}
int main()
{
    int a,b;
    int i,k;
    __int64 ans;
    GetPrim();
    scanf("%d%d",&a,&b);
    ans=1;
    for(i=0; i<cnt && a>1; ++i)
    {
        k=0;
        while(a%prim[i]==0)
        {
            k++;
            a=a/prim[i];
        }
        if(k)
            ans=(ans*Sum(prim[i],k*b+1))%MOD;
    }
    if(a>1)
        ans=(ans*Sum(a,b+1))%MOD;
    printf("%I64d\n",ans);
    return 0;
}