HDU -- 2421 Deciphering Password（基础数论）

题目vj链接

题面：

题意：
给定两个数$A,B$A,B，求$A^B$AB的各因子的因子个数的立方之和。

题解：
我们设 $d$d 为因子个数函数，$d(n)$d(n) 表示 $n$n 的正因子个数。
那么 $d$d 函数为积性函数，若$gcd(n,m)=1$gcd(n,m)=1，那么$d(nm)=d(n)*d(m)$d(nm)=d(n)∗d(m)，那么则有：
$d^3(nm)=d^3(n)*d^3(m)$d3(nm)=d3(n)∗d3(m)

我们设唯一分解$x=p_1^{e_1}*p_2^{e_2}*p_3^{e_3}*...*p_k^{e_k}$x=p1e1​​∗p2e2​​∗p3e3​​∗...∗pkek​​，那么$d(x)=(e_1+1)*(e_2+1)*(e_3+1)*...*(e_k+1)$d(x)=(e1​+1)∗(e2​+1)∗(e3​+1)∗...∗(ek​+1)

现在我们设$A^B=p_1^{e_1}*p_2^{e_2}*p_3^{e_3}*...*p_k^{e_k}$AB=p1e1​​∗p2e2​​∗p3e3​​∗...∗pkek​​，我们以以下形式表示 $A^B$AB的因子：

$(p_1^0,p_1^1,p_1^2,...,p_1^{e_1})*(p_2^0,p_2^1,p_2^2,...,p_2^{e_2})*...*(p_k^0,p_k^1,p_k^2,...,p_k^{e_k})$(p10​,p11​,p12​,...,p1e1​​)∗(p20​,p21​,p22​,...,p2e2​​)∗...∗(pk0​,pk1​,pk2​,...,pkek​​)

我们可以从每一对小括号中选择一个数来组成 $A^B$AB，且每个小括号选出来的数与其他小括号选出来的数一定都是互质的。

假设我们现在从第一个小括号里面选出来的数是$p_1^0$p10​，其后的数任选均可组成一个 $A^B$AB的因子，那么现在因子个数的立方的贡献为$((0+1)^3)*(1^3+2^3+3^3+...+(e_2+1)^3)*...*(1^3+2^3+3^3+...+(e_k+1)^3)$((0+1)3)∗(13+23+33+...+(e2​+1)3)∗...∗(13+23+33+...+(ek​+1)3)

假设我们现在从第一个小括号里面选出来的数是$p_1^1$p11​，其后的数任选均可组成一个 $A^B$AB的因子，那么现在因子个数的立方的贡献为$((1+1)^3)*(1^3+2^3+3^3+...+(e_2+1)^3)*...*(1^3+2^3+3^3+...+(e_k+1)^3)$((1+1)3)∗(13+23+33+...+(e2​+1)3)∗...∗(13+23+33+...+(ek​+1)3)

那么最终答案$ans=(1^3+2^3+3^3+...+(e_1+1)^3)*(1^3+2^3+3^3+...+(e_2+1)^3)*...*(1^3+2^3+3^3+...+(e_k+1)^3)$ans=(13+23+33+...+(e1​+1)3)∗(13+23+33+...+(e2​+1)3)∗...∗(13+23+33+...+(ek​+1)3)

我们有公式$\sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=(\frac{n*(n+1)}{2})^2$∑i=1n​i3=(∑i=1n​i)2=(2n∗(n+1)​)2

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=10007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=5010;
const int maxm=100100;
const int maxp=100100;
const int up=100100;

int cnt=0;
int tot=0;
ll p[108],e[108];
ll a,b;

void only(ll n)
{
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i) continue;
        p[++tot]=i;
        while(n%i==0)
        {
            e[tot]++;
            n/=i;
        }
    }
    if(n>1) p[++tot]=n,e[tot]=1;
    for(int i=1;i<=tot;i++)
        e[i]*=b;
}

int main(void)
{
    int tt=0;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        only(a);

        ll ans=1;
        ll res=1;
        for(int i=1;i<=tot;i++)
        {
            res=(e[i]+1)*(e[i]+2)/2;
            ans=(ans*res%mod*res)%mod;
        }
        printf("Case %d: %lld\n",++tt,ans%mod);
    }
    return 0;
}