|
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1066
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给定一个数N(N <= 10^200),求出N的阶乘的最后一位非零数字。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
题解:
找规律 + 大数模拟
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
N比较大,我一开始写了一个log5(N)*log2(N)的算法都超时了。关键还是找
规律,对于一个给定的 N,可以先将所有是5的倍数的数提出来先放在一边不管。
并且将原来是5的倍数的位置补上1 ,那么可以原来的序列就变成了0 1 2 3 4 1
6 7 8 9 1 ,现在我们将前10个数的阶乘去掉5之后的尾数列出来,得到以下
的表data[0 9] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6}。我们惊人的发现第一位
是1,最后一位是6,于是大胆的假设如果将N个数每10个分成1组(这个N个数已经
去掉了5的倍数),每组的尾数相乘都是data[0 9],并且如果第一组和第二组
都是10个元素,他们相乘的值还是6,这是显然的。因为6*6 = 6,所以这一部分
的乘积X[N]就可以通过N的尾数来确定,我们有如下公式:
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
1. X[N] = data[N] 当N < 10
2. X[N] = data[N%10] * 6 当N >= 10
其中X[N]表示1 N个数中去掉所有5的倍数后的乘积。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
然后再来看5的倍数那一部分,它们是:5*10 * 15 * 20 * 25 * 30 * 35![](http://www.cppblog.com/Images/dot.gif)
我们发现将他们提取公因子,可以写成 5^P * P!。其中P = [N/5],因为求得是
阶乘最后一位非零位,所以这里的5^P必须要用P个2来匹配掉,如果将最后的非零
为记为T[N]的话,那么T[N] = (X[N] / 2^P) * T[P]; 这里的除法不是不同意义
的除法,因为X[N]有可能是1位数,我们发现:
2^1 % 10 = 2,
2^2 % 10 = 4,
2^3 % 10 = 8,
2^4 % 10 = 6,
每四个一循环,当P == 0的时候比较特殊,2^P % 10 = 1
除上2^P其实就是乘上2^(-P),这样处理就简单了,根据循环的性质就可以将T[N]
简化成T[N] = X[N] * 2^(-P) * T[P],这样一来,算法的复杂度就只有O(log5(N))
了。并且2是每四个一循环,2^(-P) = 2^(-P % 4 + 4)。
计算T[N]只需要递归计算T[N/5]即可。
*/
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef __int64 ll;
const ll Base = (ll)100000000 * (ll)1000000000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ll val_pro[20];
ll carry_pro[5];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int TwoMod[] = {2, 4, 8, 6};
// 将5的倍数部分补1后的阶乘尾数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int data[] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct BigNum {
ll nData[14];
int nLen;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) BigNum() {nLen = 0;}
BigNum(char *str);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ModFour();
int ModTen();
void DivideFive();
void DivideTwo();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) bool operator==(BigNum b) {
if(nLen != b.nLen) return false;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < nLen; i++) {
if(nData[i] != b.nData[i])
return false;
}
return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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("");
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) BigNum::BigNum(char *S) {
int i, j = 0;
nData[nLen = 0] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int BigNum::ModFour() {
if(!nLen)
return 0;
return nData[0] % 4;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int BigNum::ModTen() {
if(!nLen)
return 0;
return nData[0] % 10;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void BigNum::DivideFive() {
if(!nLen)
return ;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = nLen-1; i >= 0; --i) {
int nCarry = (nData[i] % 5);
nData[i] /= 5;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(nCarry && i) {
nData[i-1] += carry_pro[ nCarry ];
}
}
if(!nData[nLen-1])
-- nLen;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void BigNum::DivideTwo() {
if(!nLen)
return ;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = nLen-1; i >= 0; i--) {
int nCarry = (nData[i] & 1);
nData[i] >>= 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(i && nCarry) {
nData[i-1] += Base;
}
}
if(!nData[nLen-1])
-- nLen;
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int FindNoneZeroTail(BigNum Bn) {
if(!Bn.nLen)
return 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(Bn.nLen == 1) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(Bn.nData[0] < 5) {
return data[ Bn.nData[0] ];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(Bn.nData[0] < 10) {
return data[ Bn.nData[0] ] * TwoMod[2] % 10;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int v = Bn.ModTen();
Bn.DivideFive();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int XN = data[v] * 6 % 10;
int idx = 4 - Bn.ModFour();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(idx == 0) {
idx = 4;
}
XN *= TwoMod[idx - 1];
return XN * FindNoneZeroTail(Bn) % 10;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char str[10000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%s", str) != EOF) {
BigNum X(str);
printf("%d\n", FindNoneZeroTail(X));
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|