问题描述:

你需要求出$A^B$的所有约数之和。

输入:

只有两个数A,B $(1<=A,B<=5*10^7)$

输出:

一个数,约数之和($mod 9901$)

思路:

一开始不知道算术基本定理时看得比较懵逼。。。后面才发现是傻逼题。。

首先任何大于1的正整数$N$都可以分解成$ N =p_1^{c_1}p_2^{c_2}p_3^{c_3}···p_m^{c_m} $的形式,其中$c_i$为正整数,$p_1<p_2<p_3<···<p_m$且$p_i$均为质数。根据这个我们可以有个推论就是$N$的正约数之和为$ \prod_{i=1}^m (\sum_{j=0}^{c_i} p_i ^j) $。

这样就很容易得得出这题的答案:$ ans= \prod_{i=1}^m (\sum_{j=0}^{c_i*B} p_i ^j) $。这个就可以用等比数列的求和公式来求,要注意的就是除要变成乘逆元,当逆元不存在时要特判。

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 1000005
#define mod 9901
#define LL long long
using namespace std;

LL a, b, c[MAXN][2], ans=1, cnt;

void div(LL num)
{
    for(int i=2; i*i<=num; i++)
        if(num%i==0)
        {
            c[++cnt][0]=i;
            while(num%i==0) c[cnt][1]++, num/=i;
        }
    if(num!=1) c[++cnt][0]=num, c[cnt][1]=1;
}

LL ksm(LL x, LL y)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=(x*ans)%mod;
        x=(x*x)%mod; y>>=1;
    }
    return ans;
}

LL sum(LL x, LL y)
{
    if(y==0) return 1;
    if(y&1) return (1+ksm(x, y/2+1))*sum(x, y/2)%mod;
    else return ((1+ksm(x, y/2+1))*sum(x, y/2-1)+ksm(x, y/2))%mod;
}

int main()
{
    while(scanf("%lld%lld", &a, &b)!=EOF)
    {
        div(a);
        for(int i=1; i<=cnt; i++) ans=sum(c[i][0], c[i][1]*b)*ans%mod;
        printf("%lld\n", ans);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注