ZOJ 1222 解题报告
题目大意
求一个数阶乘的最后一个非零位
样例：
- 0 ---> 1
- 1 ---> 1
- 2 ---> 2
- 26 ---> 4
- 125 ---> 8
- 3125 ---> 2
- 9999 ---> 8
初步分析
如果阶乘的过程中没有产生10的倍数（末尾也就不会出现0），那么整个阶乘阶段只需要记录乘积的最后一位即可。进一步分析可知，5是产生10的关键因子，因此，在计算的过程中需要将因子5提取出来单独考虑。
具体分析
设f(n)表示n!的最后一非零位，由上述分析可知，5是产生10的关键因子，g(n)表示阶乘过程中把所有5的倍数换成1的结果。例如:
h(n)表示g(n)的最后一位数字，很明显这个数一定不为0。
下图列出了从[0, 39]的h(n)的值：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 6 | 4 | 4 | 4 | 8 | 4 | 6 | 6 | 6 | 2 | 6 | 4 | 4 | 4 | 8 | 4 | 6 | 6 | 6 | 2 | 6 | 4 | 4 | 4 | 8 | 4 | 6 | 6 | 6 | 2 | 6 | 4 | 4 | 4 | 8 | 4 | 6 |
可以看出除了0和1以外（其实是一样的，后面会讨论）后面的都是按照一定规律的循环（每10个一循环），循环体是6 6 2 6 4 4 4 8 4 6
可知h(n)的取值范围是2、4、6、8
n的阶乘按照上述思路可以做以下的分解：
其中，表达式
是能够除尽的，因为g(n)中因子2的数量比因子5的数量要多，这里只是除掉了因子5数量的因子2，由于g(n)是去掉因子5的阶乘结果，其不会产生尾0，因此计算结果只需要保存最后一位即可。
f(n)显然应该等于
的最后一位数字，右半部分是可以递归求解的，左边部分的最后一位数字记为l(n)
l(n)其实是下面表达式的循环结果（除以2的次数不一样）
上述表达式的结果应该是个偶数（左半部分因子2没有除完），只能存在于2、4、6、8中
有如下对应关系（除以2）：
2 ---> 6 ---> 8 ---> 4 ---> 2
4 ---> 2 ---> 6 ---> 8 ---> 4
6 ---> 8 ---> 4 ---> 2 ---> 6
8 ---> 4 ---> 2 ---> 6 ---> 8
发现此对应关系也是循环结构（每4个一个循环）
代码
所有代码直接复制可AC（需要去掉//注释，不然会Compilation Error）
按照上面的分析写出如下代码：
递归代码
#include <stdio.h>
#include <string.h>
#define MAX 1000
//此数组是g(n)的最后一位即h(n)从0-9的取值
int arr_no_5[] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
//此数组是考虑n属于[0, 4]的情况，因为0！= 1、1！= 1，而不是上面的6，需要特殊考虑
int arr_small[] = {1, 1, 2, 6, 4};
//题目n的取值范围很大，因此采用字符串的形式接受，后面的运算也是大数形式的运算
char n[MAX];
int f(char *, int);
//对应上面的左半部分即l(n)
int l(char *, int);
//对应上面的h(n)，对应于数组arr_no_5的值
int h(char *, int);
//除以5，只保留整数部分和C语言中的整数除法一样
void div5(char *, int);
//对4取模运算
int mod4(char *, int);
int main(void) {
int len;
memset(n, '\0', sizeof(char) * MAX);
while (scanf("%s", n) != EOF) {
len = strlen(n);
printf("%d\n", f(n, len));
memset(n, '\0', sizeof(char) * MAX);
}
return 0;
}
int f(char n[], int len) {
char t[MAX];
memcpy(t, n, sizeof(char) * MAX);
if (len == 1 && n[0] - '0' >= 0 && n[0] - '0' <= 4) {
return arr_small[n[0] - '0'];
}
//对应上述递归公式
div5(t, len);
return (l(n, len) * f(t, strlen(t))) % 10;
}
int l(char n[], int len) {
char t[MAX];
int m = h(n, len);
int i;
int ct;
memcpy(t, n, sizeof(char) * MAX);
div5(t, len);
//h(n)除以2的结果是每4个一循环
ct = mod4(t, strlen(t));
for (i = 0; i < ct; ++i) {
//对应于上面的转换表
switch (m) {
case 6:
m = 8;
break;
case 2:
m = 6;
break;
case 4:
m = 2;
break;
case 8:
m = 4;
break;
}
}
return m;
}
int h(char n[], int len) {
return arr_no_5[n[len - 1] - '0'];
}
void div5(char n[], int len) {
char t[MAX];
int res, flag = 0;
int i;
memset(t, '\0', sizeof(char) * MAX);
for (i = 0; i < len; ++i) {
t[i] = n[len - 1 - i];
}
//先乘以2
for (i = 0; i < len; ++i) {
res = (t[i] - '0') * 2 + flag;
flag = res / 10;
res %= 10;
t[i] = res + '0';
}
if (flag) {
t[len] = flag + '0';
len++;
}
for (i = 1; i < len; ++i) {
t[i - 1] = t[i];
}
t[--len] = '\0';
memset(n, '\0', sizeof(char) * MAX);
//再除以10，即去掉个位
for (i = 0; i < len; ++i) {
n[i] = t[len - 1 - i];
}
return ;
}
int mod4(char n[], int len) {
int m;
//模4只与后两位有关系，其值等于后面二位模4的值
m = n[len - 1] + n[len - 2] * 10;
return m % 4;
}
上面的代码有递归，其实非递归也很好写，用循环即可代替：
非递归代码
#include <stdio.h>
#include <string.h>
#define MAX 1000
//此数组是g(n)的最后一位即h(n)从0-9的取值
int arr_no_5[] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
//此数组是考虑n属于[0, 4]的情况，因为0！= 1、1！= 1，而不是上面的6，需要特殊考虑
int arr_small[] = {1, 1, 2, 6, 4};
//题目n的取值范围很大，因此采用字符串的形式接受，后面的运算也是大数形式的运算
char n[MAX];
int f(char *, int);
//对应上面的左半部分即l(n)
int l(char *, int);
//对应上面的h(n)，对应于数组arr_no_5的值
int h(char *, int);
//除以5，只保留整数部分和C语言中的整数除法一样
void div5(char *, int);
//对4取模运算
int mod4(char *, int);
int main(void) {
int len;
memset(n, '\0', sizeof(char) * MAX);
while (scanf("%s", n) != EOF) {
len = strlen(n);
printf("%d\n", f(n, len));
memset(n, '\0', sizeof(char) * MAX);
}
return 0;
}
int f(char n[], int len) {
int res = 1;
char t[MAX];
memcpy(t, n, sizeof(char) * MAX);
if (len == 1 && n[0] - '0' >= 0 && n[0] - '0' <= 4) {
return arr_small[n[0] - '0'];
}
//对应上述递归公式，其他都是一样的，用循环代替递归
while (strlen(t)) {
res = (l(t, strlen(t)) * res) % 10;
div5(t, strlen(t));
}
return res;
}
int l(char n[], int len) {
char t[MAX];
int m = h(n, len);
int i;
int ct;
memcpy(t, n, sizeof(char) * MAX);
div5(t, len);
//h(n)除以2的结果是每4个一循环
ct = mod4(t, strlen(t));
for (i = 0; i < ct; ++i) {
//对应于上面的转换表
switch (m) {
case 6:
m = 8;
break;
case 2:
m = 6;
break;
case 4:
m = 2;
break;
case 8:
m = 4;
break;
}
}
return m;
}
int h(char n[], int len) {
return arr_no_5[n[len - 1] - '0'];
}
void div5(char n[], int len) {
char t[MAX];
int res, flag = 0;
int i;
memset(t, '\0', sizeof(char) * MAX);
for (i = 0; i < len; ++i) {
t[i] = n[len - 1 - i];
}
//先乘以2
for (i = 0; i < len; ++i) {
res = (t[i] - '0') * 2 + flag;
flag = res / 10;
res %= 10;
t[i] = res + '0';
}
if (flag) {
t[len] = flag + '0';
len++;
}
for (i = 1; i < len; ++i) {
t[i - 1] = t[i];
}
t[--len] = '\0';
memset(n, '\0', sizeof(char) * MAX);
//再除以10，即去掉个位
for (i = 0; i < len; ++i) {
n[i] = t[len - 1 - i];
}
return ;
}
int mod4(char n[], int len) {
int m;
//模4只与后两位有关系，其值等于后面二位模4的值
m = n[len - 1] + n[len - 2] * 10;
return m % 4;
}
网上代码
在网上看到最多的能够AC的代码，思路和上面是一样的但是写法相当简洁，特意分析学习（注释是后加的）
代码如下：
#include <stdio.h>
#include <string.h>
int mod[20] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};
char n[1000];
//存放n的逆序，方便做计算
int a[1000];
int main(void) {
int i, c, t, len;
while (scanf("%s", n) != EOF) {
t = 1;
len = strlen(n);
for (i = 0; i < len; i++)
a[i] = n[len - 1 - i] - '0';
while (len) {
len -= !a[len - 1];
//对应于上面递归公式
t = t * mod[a[1] % 2 * 10 + a[0]] % 10;
//将n除以5
for (c = 0, i = len - 1; i >= 0; i--) {
c = c * 10 + a[i];
a[i] = c / 5;
c %= 5;
}
}
printf("%d\n", t);
}
return 0;
}
前面分析了h(n)是个长度为10的循环，而h(n)/2是长度为4的循环，因此l(n)是长度为20（10和4的最小公倍数）的循环，其循环体是6 6 2 6 4 2 2 4 2 8 4 4 8 4 6 8 8 6 8 2
而0! = 1、1! = 1不是上面的6，因此需要特殊处理
#include <stdio.h>
#include <string.h>
//对于0、1的特殊处理
int small[] = {1, 1};
//l(n)的循环
int mod[20] = {6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};
char n[1000];
//存取n的逆序，方便后续计算
int a[1000];
int main() {
int i, c, t, len;
while (scanf("%s", n) != EOF) {
t = 1;
len = strlen(n);
//特殊处理
if (len == 1 && (n[0] - '0' == 0 || n[0] - '0' == 1)) {
t = small[n[0] - '0'];
} else {
//逆序n方便处理
for (i = 0; i < len; i++)
a[i] = n[len - 1 - i] - '0';
while (len) {
//n除以5是0时退出循环，即是(n/5)的阶乘计算完了，相应的长度也就是0
len -= !a[len - 1];
//对应于上面的递归公式
t = t * mod[a[1] % 2 * 10 + a[0]] % 10;
//计算n除以5
for (c = 0, i = len - 1; i >= 0; i--)
c = c * 10 + a[i], a[i] = c / 5, c %= 5;
}
}
printf("%d\n", t);
}
return 0;
}
观察到网上代码的l(n)循环最前面的两位是1、1，其实这里的1和6是没有区别的，6和2、4、6、8相乘结果的最后一位还是原来本身，1也有这样的效果，再考虑公式
若在n >= 10的情况下，左半部分是6或者是1，乘以右边的结果都是一样的，也就是右边结果本身
阶乘结果的最后一位非零数肯定是2、4、6、8中的一个
因此mod数组中6和1是可以互换的，考虑到0、1的特殊情况，采用网上的1 1 2 6 4 2 2 4 2 8 4 4 8 4 6 8 8 6 8 2是比较合理的，不需要额外的特殊处理，代码简洁
把mod数组中的6全部换成1：
#include <stdio.h>
#include <string.h>
//在n小于10的情况下的特殊处理，虽然0、1是一样的，但是有不一样的，比如3
//没有做特殊处理在HDUOJ上是WA，但是在ZOJ是AC的。。。。。。
int small[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
int mod[20] = {1, 1, 2, 1, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 1, 8, 8, 1, 8, 2};
char n[1000];
int a[1000];
int main() {
int i, c, t, len;
while (scanf("%s", n) != EOF) {
t = 1;
len = strlen(n);
if (len == 1 && n[0] - '0' >= 0 && n[0] - '0' <= 9) {
t = small[n[0] - '0'];
}else {
for (i = 0; i < len; i++)
a[i] = n[len - 1 - i] - '0';
while (len) {
len -= !a[len - 1];
t = t * mod[a[1] % 2 * 10 + a[0]] % 10;
for (c = 0, i = len - 1; i >= 0; i--)
c = c * 10 + a[i], a[i] = c / 5, c %= 5;
}
}
printf("%d\n", t);
}
return 0;
}
把mod数组中的1全部换成6，代码前面已经有了
总结
这种类型的题先写出数学公式，根据数学公式来写代码就简单了，中间处理过程或者处理结果一般都会存在某种规律，最后注意大数的处理
网友评论