数论:
求n的阶乘的最右边非零数字
若出现0,必定是由于2*5引起的(且2,5同时出现,若只出现2或5不会出现0)
思路:
- 遍历所有因子,且把2,5的倍数的因子都约分至,不含2,5因子。
- 由于最后取的是最右边的非零数,即非零个位,我们直到,结果的个位数仅由个位数相乘%10得到
关键代码
res=res*tem%10
- 最后的结果,任意一个数,它的含2因子的因数一定比5多,所以我们需要把那些并不是同时和5出现的2再乘回来
关键代码:
for(int i=0;i<(num_2-num_5);i++) res=res*2%10
不过我们时刻要记得,我们最后的结果只取个位,即res%10
代码区:
#include <iostream>
using namespace std;
const int N=1010;
int num_2,num_5;
int main()
{
int n;
cin>>n;
int res=1;
for(int i=1;i<=n;i++)
{
int tem=i;//把所有因子中是2,5 的倍数的因子化简到非2,5倍数的因子
while(!(tem%2))
{
tem/=2;
++num_2;
}
while(!(tem%5))
{
tem/=5;
++num_5;
}
res=res*tem%10;
}
for(int i=0;i<(num_2-num_5);i++) res=res*2%10;
cout<<res;
}