试题题目：
本题答案：2430
解题思路：
- 第一次编写程序：
题目给出的
n
n
n数值为
16
16
16位数字，
C
C
C语言中有类型
l
o
n
g
long
long
l
o
n
g
long
long
i
n
t
int
int，其范围为
−
9223372036854775808
-9223372036854775808
−9223372036854775808~
9223372036854775807
9223372036854775807
9223372036854775807，为
19
19
19位数值完全可以存储
n
n
n；观察题目给出的例知：不需要进行去重处理。即虽因数相同，但所在位置不同，属于两种不同的方案。编写一个程序计算
n
n
n的所有因数，发现因数个数为
128
128
128个，可以简单地使用暴力的方法（三重循环），当符合
“
n
=
“n=
“n=因数1
∗
*
∗因数2
∗
*
∗因数3
”
”
”式子时，统计变量
s
u
m
sum
sum加一。代码如下：
#include
#include
#define n 2021041820210418
long long int inshu[1000];
int sum = 0;
int main(){
long long int geshu;
int i,j,z;
geshu = factor(n);
for(i=0;i= 0){ //把另一半的因数补齐
inshu[k++] = N / inshu[i];
}
return k;
}
- 第二次编写程序（第一次优化）：
暴力求解的方法，其时间复杂度为
O
(
n
3
)
O(n^3)
O(n3)，造成了时间上的消耗，对上一个算法进行优化，优化方法为：通过调用
f
a
c
t
o
r
(
)
factor()
factor() 函数，找出n的所有因数，把
n
n
n拆分为
“
n
=
“n=
“n=因数1
∗
*
∗因数2
∗
*
∗因数3
”
”
”的式子；在对因数2调用
f
a
c
t
o
r
(
)
factor()
factor()找出因数2的所有因数，把因数2拆分为
“
“
“因数2
=
=
=因数21
∗
*
∗因数22
”
”
” 的式子；把这两个式子合并，便可以得出
“
n
=
“n=
“n=因数1
∗
*
∗因数2
∗
*
∗因数3
”
”
””，统计式子的个数，便可以得出答案。代码：
#include
#include
#define n 2021041820210418
int sum = 0; //统计式子个数的变量
long long int *factor(long long int N,long long int inshu[1000]);
int main(){
long long int yinshu[1000] = {0}; //存储n的所有的因数；
int i,j;
factor(n,yinshu);
for(i=0; i= 0){ //把另一半的因数补齐
inshu[k++] = N / inshu[i];
}
inshu[999] = k; //计算之前跑一下程序发现n因数不超过900个,可知k就是N的因子个数，并把它储存与inshu数组的最后一个值，目的为了传回到主函数中。
return inshu;
}
- 第三次编写程序（第二次优化）
通过深度分析，比较上述两个算法，可以对以上算法进一步简化。
优化过程：因不需要去重，假设
f
1
∗
f
2
∗
f
3
=
n
f1 * f2 * f3 = n
f1∗f2∗f3=n ，根据这一个式子直接可以得出另外五个式子：“
f
1
∗
f
3
∗
f
2
=
n
f1 * f3 * f2 = n
f1∗f3∗f2=n ”、“
f
2
∗
f
1
∗
f
3
=
n
f2 * f1 * f3 = n
f2∗f1∗f3=n”、“
f
2
∗
f
3
∗
f
1
=
n
f2 * f3 * f1 = n
f2∗f3∗f1=n”、“
f
3
∗
f
1
∗
f
2
=
n
f3 * f1 * f2 = n
f3∗f1∗f2=n” 以及 “
f
3
∗
f
2
∗
f
1
=
n
f3 * f2 * f1 = n
f3∗f2∗f1=n”。
注意：
(1)当
f
1
=
f
2
=
f
3
f1 =f2 = f3
f1=f2=f3时，
f
1
∗
f
2
∗
f
3
=
n
f1 * f2 *f3 = n
f1∗f2∗f3=n 只能算作一个式子；
(2)当
f
1
=
f
2
f1 = f2
f1=f2 或者
f
1
=
f
3
f1=f3
f1=f3 或者
f
2
=
f
3
f2=f3
f2=f3时,
f
1
∗
f
2
∗
f
3
=
n
f1 * f2 * f3 = n
f1∗f2∗f3=n 改变位置后共得出三个式子；
(3)当
f
1
≠
f
2
≠
f
3
f1 neq f2 neq f3
f1=f2=f3时，
f
1
∗
f
2
∗
f
3
=
n
f1 * f2 * f3 = n
f1∗f2∗f3=n ,可以算作六个不同式子；
(4)为了避免重复计算，需要保证
f
1
≤
f
2
≤
f
3
f1 le f2 le f3
f1≤f2≤f3；
以上两个算法，都使用了函数和数组，求因数再储存因数，消耗大量的存储空间。而求因数的过程特别简单，就是拿这个数(
n
n
n)除以小于它的数值(
i
i
i)，如果能够被整除(
n
m
o
d
i
=
0
n bmod i = 0
nmodi=0)，那么
i
i
i就是它的第一个因数，
n
/
i
n/i
n/i就是它的第二个因数(
j
j
j)。用一个循环即可实现，循环条件设置为(
i
≤
s
q
r
t
(
n
)
i le sqrt(n)
i≤sqrt(n))，保证了第一个因数小于第二个因数；再对第二个因数使用同样的循环，寻找出第二个因数的因数。第三个因数就是
n
/
i
/
j
n/i/j
n/i/j.
具体代码：
#include
#include
#define n 2021041820210418
int main(){
long long int i,j;
int sum = 0; //统计式子个数的变量
for(i=1;i<=sqrt(n);i++){
if(n%i == 0){ //i是n的第一个因数
for(j=i;j<=sqrt(n/i);j++){ //j从i开始循环,保证了i<=j
if(n/i%j == 0){ //j是n的第二个因数
if(i==j && j==n/i/j){sum++;}
else if(i==j || j==n/i/j || i==n/i/j){sum+=3;}
else {sum+=6;}
//printf("%lld %lld %lld %d n",i,j,n/i/j,sum); //检测代码
}
}
}
}
printf("%d",sum);
}
