|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1066
  /**//*
 題意：
給定一個(gè)數(shù)N(N <= 10^200)，求出N的階乘的最后一位非零數(shù)字。
題解：
找規(guī)律 + 大數(shù)模擬
思路：
N比較大，我一開始寫了一個(gè)log5(N)*log2(N)的算法都超時(shí)了。關(guān)鍵還是找
規(guī)律，對于一個(gè)給定的 N，可以先將所有是5的倍數(shù)的數(shù)提出來先放在一邊不管。
并且將原來是5的倍數(shù)的位置補(bǔ)上1 ，那么可以原來的序列就變成了0 1 2 3 4 1
6 7 8 9 1 ，現(xiàn)在我們將前10個(gè)數(shù)的階乘去掉5之后的尾數(shù)列出來，得到以下
的表data[09] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6}。我們驚人的發(fā)現(xiàn)第一位
是1，最后一位是6，于是大膽的假設(shè)如果將N個(gè)數(shù)每10個(gè)分成1組（這個(gè)N個(gè)數(shù)已經(jīng)
去掉了5的倍數(shù)），每組的尾數(shù)相乘都是data[09]，并且如果第一組和第二組
都是10個(gè)元素，他們相乘的值還是6，這是顯然的。因?yàn)?*6 = 6，所以這一部分
的乘積X[N]就可以通過N的尾數(shù)來確定，我們有如下公式：
1. X[N] = data[N] 當(dāng)N < 10
2. X[N] = data[N%10] * 6 當(dāng)N >= 10
其中X[N]表示1N個(gè)數(shù)中去掉所有5的倍數(shù)后的乘積。
然后再來看5的倍數(shù)那一部分，它們是：5*10 * 15 * 20 * 25 * 30 * 35
我們發(fā)現(xiàn)將他們提取公因子，可以寫成 5^P * P!。其中P = [N/5]，因?yàn)榍蟮檬?br>階乘最后一位非零位，所以這里的5^P必須要用P個(gè)2來匹配掉，如果將最后的非零
為記為T[N]的話，那么T[N] = (X[N] / 2^P) * T[P]; 這里的除法不是不同意義
的除法，因?yàn)閄[N]有可能是1位數(shù)，我們發(fā)現(xiàn)：
2^1 % 10 = 2，
2^2 % 10 = 4，
2^3 % 10 = 8，
2^4 % 10 = 6，
每四個(gè)一循環(huán)，當(dāng)P == 0的時(shí)候比較特殊，2^P % 10 = 1
除上2^P其實(shí)就是乘上2^(-P)，這樣處理就簡單了，根據(jù)循環(huán)的性質(zhì)就可以將T[N]
簡化成T[N] = X[N] * 2^(-P) * T[P]，這樣一來，算法的復(fù)雜度就只有O(log5(N))
了。并且2是每四個(gè)一循環(huán)，2^(-P) = 2^(-P % 4 + 4)。
計(jì)算T[N]只需要遞歸計(jì)算T[N/5]即可。
 */
 #include <iostream>
using namespace std;
typedef __int64 ll;
const ll Base = (ll)100000000 * (ll)1000000000;
ll val_pro[20];
ll carry_pro[5];
int TwoMod[] = {2, 4, 8, 6};
// 將5的倍數(shù)部分補(bǔ)1后的階乘尾數(shù)
int data[] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
struct BigNum {
ll nData[14];
int nLen;
  BigNum(){nLen = 0;}
BigNum(char *str);
int ModFour();
int ModTen();
void DivideFive();
void DivideTwo();
bool operator==(BigNum b) {
if(nLen != b.nLen) return false;
int i;
for(i = 0; i < nLen; i++) {
if(nData[i] != b.nData[i])
return false;
 }
return true;
}
void print(){
printf("%d",nLen==0?0:nData[nLen-1]);
for(int i=nLen-2;i>=0;i--)
for(ll j=Base/10;j>0;j/=10)
printf("%d",nData[i]/j%10);
puts("");
}
};
BigNum::BigNum(char *S) {
int i, j = 0;
nData[nLen = 0] = 0;
for (i = strlen(S)-1; i >= 0; --i) {
nData[nLen] += (S[i] - '0') * val_pro[j];
++j;
if (val_pro[j] >= Base) j = 0, nData[++nLen] = 0;
}
if (nData[nLen] > 0) ++nLen;
}
int BigNum::ModFour() {
if(!nLen)
return 0;
return nData[0] % 4;
}
int BigNum::ModTen() {
if(!nLen)
return 0;
return nData[0] % 10;
}
void BigNum::DivideFive() {
if(!nLen)
return ;
int i;
for(i = nLen-1; i >= 0; --i) {
int nCarry = (nData[i] % 5);
nData[i] /= 5;
if(nCarry && i) {
nData[i-1] += carry_pro[ nCarry ];
}
}
if(!nData[nLen-1])
-- nLen;
return ;
}
void BigNum::DivideTwo() {
if(!nLen)
return ;
int i;
for(i = nLen-1; i >= 0; i--) {
int nCarry = (nData[i] & 1);
nData[i] >>= 1;
if(i && nCarry) {
nData[i-1] += Base;
}
}
if(!nData[nLen-1])
-- nLen;
return ;
}
int FindNoneZeroTail(BigNum Bn) {
if(!Bn.nLen)
return 1;
if(Bn.nLen == 1) {
if(Bn.nData[0] < 5) {
return data[ Bn.nData[0] ];
}else if(Bn.nData[0] < 10){
return data[ Bn.nData[0] ] * TwoMod[2] % 10;
}
}
int v = Bn.ModTen();
Bn.DivideFive();
int XN = data[v] * 6 % 10;
int idx = 4 - Bn.ModFour();
if(idx == 0) {
idx = 4;
}
XN *= TwoMod[idx - 1];
return XN * FindNoneZeroTail(Bn) % 10;
}
char str[10000];
int main() {
int i, j;
val_pro[0] = 1;
for(i = 1; i < 20; i++)
val_pro[i] = val_pro[i-1] * 10;
for(i = 0; i < 5; i++)
carry_pro[i] = i * Base;
while(scanf("%s", str) != EOF) {
BigNum X(str);
printf("%d\n", FindNoneZeroTail(X));
}
return 0;
}
|