hdu-2421 Deciphering Password 数学姿势

给定A,B，对于A^B的每一个因子，M为其因子的因子数的三次方求和。

容易推导得出A^B的每一个因子都是A的质因子的组合（质因子可重复利用），其因子数自然等于所使用的每个质因子的数量乘积。

假设A由质因子a1,a2,a3组合而成，对应数量为k1,k2,k3，那么A的因子数为(k1+1)*(k2+1)*(k3+1)，同理A的因子的因子数为(k1+1)*(k2+1)*k3+1,(k1+1)*k2*(k3+1),k1*(k2+1)*(k3+1),(k1+1)*k2*k3以此类推。

我们可以发现其为(1+2+3...k1+1)*(1+2+3...k2+1)*(1+2+3...k3+1)的展开。对于这里的每一项，我们可以用求和公式(n*(n+1)/2)^2来求解。

对于拆解一个数的质因数，我们只需要枚举到srqt(n)即可，因为至多只有一个质因数大于sqrt(n) n不断做除法剩下的数即是这个质因数，如果有两个质因数x1,x2大于sqrt(n)，那一定有n>=x1*x2与x1>sqrt(n) x2>sqrt(n)相悖。

#include <iostream>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <cstdio>

#include <algorithm>

#define LL long long

using namespace std;

const LL N = ;

const LL mod = ;

LL cube(LL num)

{

    return (num*(num + ) / )%mod*(num*(num + ) / );

}

vector<LL> su;

bool vis[N];

int main() {

    //cin.sync_with_stdio(false);

    LL a,b;

    fill(vis, vis + N, true);

    vis[] = vis[] = false;

    for(LL i=;i<N;i++)

        if (vis[i])

        {

            su.push_back(i);

            for (LL j = i * ; j < N; j *= i)

                vis[i] = false;

        }

    int cas = ;

    while (scanf("%lld%lld",&a,&b)!=EOF)

    {

        map<LL, LL> mp;

        for (LL i = ; i < su.size() && su[i]*su[i] <= a; i++)

        {

            while (a%su[i] == )

                cout << su[i] << endl, mp[su[i]]++, a /= su[i];

        }

        if (a > )mp[a]++;

        LL ans = ;

        for (map<LL, LL>::iterator it = mp.begin(); it != mp.end(); it++)

        {

            it->second *= b, it->second++;

            it->second %= mod;

            //cout << it->second << endl;

            ans *= cube(it->second);

            ans %= mod;

        }

        printf("Case %d: %lld\n", cas++, ans);

        //cout << "Case " << cas++<<": ";

        //cout << ans << endl;

    }

    return ;

}