ZOJ 1222 解題報告
題目大意
求一個數(shù)階乘的最后一個非零位
樣例：
- 0 ---> 1
- 1 ---> 1
- 2 ---> 2
- 26 ---> 4
- 125 ---> 8
- 3125 ---> 2
- 9999 ---> 8
初步分析
如果階乘的過程中沒有產(chǎn)生10的倍數(shù)（末尾也就不會出現(xiàn)0），那么整個階乘階段只需要記錄乘積的最后一位即可。進(jìn)一步分析可知，5是產(chǎn)生10的關(guān)鍵因子，因此，在計算的過程中需要將因子5提取出來單獨(dú)考慮。
具體分析
設(shè)f(n)表示n!的最后一非零位，由上述分析可知，5是產(chǎn)生10的關(guān)鍵因子，g(n)表示階乘過程中把所有5的倍數(shù)換成1的結(jié)果。例如:
h(n)表示g(n)的最后一位數(shù)字，很明顯這個數(shù)一定不為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以外（其實(shí)是一樣的，后面會討論）后面的都是按照一定規(guī)律的循環(huán)（每10個一循環(huán)），循環(huán)體是6 6 2 6 4 4 4 8 4 6
可知h(n)的取值范圍是2、4、6、8
n的階乘按照上述思路可以做以下的分解：
其中，表達(dá)式
是能夠除盡的，因為g(n)中因子2的數(shù)量比因子5的數(shù)量要多，這里只是除掉了因子5數(shù)量的因子2，由于g(n)是去掉因子5的階乘結(jié)果，其不會產(chǎn)生尾0，因此計算結(jié)果只需要保存最后一位即可。
f(n)顯然應(yīng)該等于
的最后一位數(shù)字，右半部分是可以遞歸求解的，左邊部分的最后一位數(shù)字記為l(n)
l(n)其實(shí)是下面表達(dá)式的循環(huán)結(jié)果（除以2的次數(shù)不一樣）
上述表達(dá)式的結(jié)果應(yīng)該是個偶數(shù)（左半部分因子2沒有除完），只能存在于2、4、6、8中
有如下對應(yīng)關(guān)系（除以2）：
2 ---> 6 ---> 8 ---> 4 ---> 2
4 ---> 2 ---> 6 ---> 8 ---> 4
6 ---> 8 ---> 4 ---> 2 ---> 6
8 ---> 4 ---> 2 ---> 6 ---> 8
發(fā)現(xiàn)此對應(yīng)關(guān)系也是循環(huán)結(jié)構(gòu)（每4個一個循環(huán)）
代碼
所有代碼直接復(fù)制可AC（需要去掉//注釋，不然會Compilation Error）
按照上面的分析寫出如下代碼：
遞歸代碼
#include <stdio.h>
#include <string.h>
#define MAX 1000
//此數(shù)組是g(n)的最后一位即h(n)從0-9的取值
int arr_no_5[] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
//此數(shù)組是考慮n屬于[0, 4]的情況，因為0！= 1、1！= 1，而不是上面的6，需要特殊考慮
int arr_small[] = {1, 1, 2, 6, 4};
//題目n的取值范圍很大，因此采用字符串的形式接受，后面的運(yùn)算也是大數(shù)形式的運(yùn)算
char n[MAX];
int f(char *, int);
//對應(yīng)上面的左半部分即l(n)
int l(char *, int);
//對應(yīng)上面的h(n)，對應(yīng)于數(shù)組arr_no_5的值
int h(char *, int);
//除以5，只保留整數(shù)部分和C語言中的整數(shù)除法一樣
void div5(char *, int);
//對4取模運(yùn)算
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'];
}
//對應(yīng)上述遞歸公式
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的結(jié)果是每4個一循環(huán)
ct = mod4(t, strlen(t));
for (i = 0; i < ct; ++i) {
//對應(yīng)于上面的轉(zhuǎn)換表
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只與后兩位有關(guān)系，其值等于后面二位模4的值
m = n[len - 1] + n[len - 2] * 10;
return m % 4;
}
上面的代碼有遞歸，其實(shí)非遞歸也很好寫，用循環(huán)即可代替：
非遞歸代碼
#include <stdio.h>
#include <string.h>
#define MAX 1000
//此數(shù)組是g(n)的最后一位即h(n)從0-9的取值
int arr_no_5[] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
//此數(shù)組是考慮n屬于[0, 4]的情況，因為0！= 1、1！= 1，而不是上面的6，需要特殊考慮
int arr_small[] = {1, 1, 2, 6, 4};
//題目n的取值范圍很大，因此采用字符串的形式接受，后面的運(yùn)算也是大數(shù)形式的運(yùn)算
char n[MAX];
int f(char *, int);
//對應(yīng)上面的左半部分即l(n)
int l(char *, int);
//對應(yīng)上面的h(n)，對應(yīng)于數(shù)組arr_no_5的值
int h(char *, int);
//除以5，只保留整數(shù)部分和C語言中的整數(shù)除法一樣
void div5(char *, int);
//對4取模運(yùn)算
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'];
}
//對應(yīng)上述遞歸公式，其他都是一樣的，用循環(huán)代替遞歸
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的結(jié)果是每4個一循環(huán)
ct = mod4(t, strlen(t));
for (i = 0; i < ct; ++i) {
//對應(yīng)于上面的轉(zhuǎn)換表
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只與后兩位有關(guān)系，其值等于后面二位模4的值
m = n[len - 1] + n[len - 2] * 10;
return m % 4;
}
網(wǎng)上代碼
在網(wǎng)上看到最多的能夠AC的代碼，思路和上面是一樣的但是寫法相當(dāng)簡潔，特意分析學(xué)習(xí)（注釋是后加的）
代碼如下：
#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];
//對應(yīng)于上面遞歸公式
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的循環(huán)，而h(n)/2是長度為4的循環(huán)，因此l(n)是長度為20（10和4的最小公倍數(shù)）的循環(huán)，其循環(huán)體是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)的循環(huá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的逆序，方便后續(xù)計算
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時退出循環(huán)，即是(n/5)的階乘計算完了，相應(yīng)的長度也就是0
len -= !a[len - 1];
//對應(yīng)于上面的遞歸公式
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;
}
觀察到網(wǎng)上代碼的l(n)循環(huán)最前面的兩位是1、1，其實(shí)這里的1和6是沒有區(qū)別的，6和2、4、6、8相乘結(jié)果的最后一位還是原來本身，1也有這樣的效果，再考慮公式
若在n >= 10的情況下，左半部分是6或者是1，乘以右邊的結(jié)果都是一樣的，也就是右邊結(jié)果本身
階乘結(jié)果的最后一位非零數(shù)肯定是2、4、6、8中的一個
因此mod數(shù)組中6和1是可以互換的，考慮到0、1的特殊情況，采用網(wǎng)上的1 1 2 6 4 2 2 4 2 8 4 4 8 4 6 8 8 6 8 2是比較合理的，不需要額外的特殊處理，代碼簡潔
把mod數(shù)組中的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數(shù)組中的1全部換成6，代碼前面已經(jīng)有了
總結(jié)
這種類型的題先寫出數(shù)學(xué)公式，根據(jù)數(shù)學(xué)公式來寫代碼就簡單了，中間處理過程或者處理結(jié)果一般都會存在某種規(guī)律，最后注意大數(shù)的處理
