洛谷 P2715 约数和

给出a和b求a^b的约数和。

题目描述

输入输出格式

输入格式：

一行两个数a,b。

输出格式：

一个数表示结果对 9901 的模。

输入输出样例

输入样例#1：

2 3

输出样例#1：

说明

对于 30%的数据，a,b≤ 10 对于 100%的数据，0 ≤ a,b ≤ 50 000 000

早上听大爷讲完数论马上回来补了一道

这题呢我们首先可以吧a质因数分解表示为p1^c1 × p2^c2 ×……× pn^cn

那么a^b就可以表示为p1^(c1*B) × p2^(c2*B) ×……× pn^(cn*B)

A^B的约数表示为p1^k1 × p2^k2 ×……× pn^kn，其中0<=ki<=ci*B

那么所有的约数和就是(1+p1+p1^2+……+p1^(c1*B)) × (1+p2+p2^2+……+p2^(c2*B)) ×……× (1+pn+pn^2+……+pn^(cn*B))

这个拿乘法定律什么的搞一下就可以得到了哇

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int mod=;

LL read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,m,ans=;

LL sum[],h[],cnt;

LL qmod(LL a,LL b){

    LL ans=;

    while(b){

        if(b&) ans=ans*a%mod;

        b>>=; a=a*a%mod;

    }

    return ans;

}

void prepare(){

    LL v=n;

    for(int i=;i<=v;i++)if(n%i==){

        sum[++cnt]=i;

        h[cnt]++;

        n/=i;

        while(n%i==) h[cnt]++,n/=i;

        h[cnt]*=m;

        if(!n) return ;

    }

}

int main()

{

    n=read(); m=read(); prepare();

    //for(int i=1;i<=cnt;i++) printf("[%lld %lld]\n",sum[i],h[i]);

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

        LL q=qmod(sum[i]-,mod-),p=qmod(sum[i],h[i]+)-;

        ans=ans*p%mod*q%mod;

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

    return ;

}