这题的大意就是 给出一个数n, 找到它所有的因子， 然后把这些（因子的因子数）的立方和求出来。
题目的时限虽然很宽，但是数据很BT。首先，公式必须找出来。
证明如下：
先将n质因数分解成形如n = a ^m * b ^ p * c ^q *........;
那么要求的结果为函数g(x)的值;
我们以n有2个质因数为例子；
g(n) = g(a ^m * b ^p ) ;
设求因子个数的立方的函数为f(x);
然后找到所有的因子并计算和;
g(a ^ m * b ^ p ) = f( a ^ m * b ^ p ) + f( a ^ (m - 1) * b ^ p ) + f( a ^ (m - 2) * b ^ p ) +...... + f (a ^ 0 * b ^ p) + f(a ^m * b ^ (p - 1)) + f(a ^(m - 1) * b ^ (p - 1)) ......+ f(a ^ 0 * b ^ (p - 1)) +...............+f(a ^ m * b ^ 0) + f(a
^ (m - 1) * b ^ 0) +.........f(a ^ 0 * b ^ 0); //// ①式
注意 这个序列里有 （m + 1） * ( n + 1 ) 个数， 所有的因子都表示出来了；
我们再观察f(x)的性质， 可以发现一个很重要的性质，如果 x, y互质，那么f( x * y ) = f(x) * f(y); 这个称为积性函数， 实际上自己观察规律就能找到这个性质；
我们再根据这个性质 就可以合并①式了；
g(a ^m * b ^p ) = (f(a ^m) + f(a ^ ( m - 1)) + f(a ^ (m - 2 ) ) + ..... + f(a ^ 0)) * (f(b ^p) + f(b ^ ( p - 1)) + f(b ^ (p - 2 ) ) + ..... + f(b ^ 0));
对于一个类似于x ^ y的因子数，答案是显而易见的 y + 1;
那么g(a ^m * b ^p ) = (1^3 + 2 ^ 3 + ..... + m ^ 3 + (m + 1)^ 3) * (1^3 + 2 ^ 3 + ..... + p ^ 3 + (p + 1)^ 3) ;
而立方和公式为 [(x * (x + 1)) / 2] ^ 2;
那么g(a ^m * b ^p ) = [((m + 2)* (m + 1)) / 2] ^ 2 * [((p + 2) * (p+ 1)) / 2] ^ 2;
g(n) 就求出来了。
我们可以得到一个普遍规律了
如果一个合数能被分解为 a ^ m * b ^ n * c ^ p *.............(a, b, c ......均为素数, m, n, p.....均为自然数)
那么题目要求的结果就是 [((m + 2)* (m + 1)) / 2] ^ 2 * [((n + 2) * (n+ 1)) / 2] ^ 2 * [((p + 2) * (p+ 1)) / 2] ^ 2 *.............
我的代码如下， 代码功底还很浅薄，写的比较丑，而且还用了1s多才过的 比较神奇的是用g++交会达到2s多， 而且用getchar() 优化输入也没降时间，很神奇
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
bool tag[5000001];
int p[4000001];
int cnt;
void get_prime() //筛出5000000内素数
{
cnt = 0;
tag[1] = 1;
for (int i = 2; i < 5000000; i++)
{
if (!tag[i])
p[cnt++] = i;
for (int j = 0; j < cnt && p[j] * i < 5000000; j++)
{
tag[i*p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
int t, n, i;
get_prime();
scanf("%d", &t);
while(t--)
{
int nt = 0;
scanf("%d", &n);
int ans = 1;
if(!tag[n]) ans = 9; // 如果是素数，结果就是9
else
{
for(i = 0; i < cnt && p[i] * p[i] <= n; i++)
{
if(n % p[i] == 0)
{
int ct = 0;
while(n % p[i] == 0)
{
n /= p[i];
ct++;
}
ans = ans * (ct + 1) * (ct + 1) * (ct + 2) * (ct + 2) / 4;
}
}
if(!tag[n])
ans = ans * 9;
}
printf("%d\n", ans);
}
return 0;
}
题外话：
说一下这个线性筛素数的问题
利用了每个合数必有一个最小素因子。
每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%pr[j]==0)break;
pr数组中的素数是递增的,当i能整除pr[j]，那么i*pr[j+1]这个合数肯定被pr[j]乘以某个数筛掉。
因为i中含有pr[j],pr[j]比pr[j+1]小。接下去的素数同理。所以不用筛下去了。
在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。