450
hdu 1066 Last non-zero Digit in N!
這個方法是參考https://blog.csdn.net/fengyu0556/article/details/5615129 這裏的。
證明和推到都在那裏麵，隻是那邊最後的代碼沒有注釋和其所說寫的又有些出入，所以就貼上我的代碼，好理解寫
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
const int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};//乘6除2後的規律,每20個一循環，因為循環節一個是10，一個是4
int a[200];
int calc(char *s)
{
int i,len=strlen(s);
if(len==1)return mod[s[0]-'0'];
for(i=0;i<len;i++)
a[i]=s[len-1-i]-'0';
int ans=1,j,c;
for(;len;len-=!a[len-1])//判斷第一位是否為0,循環代替遞歸
{
ans=(ans*mod[(a[1]&1)*10+a[0]])%10;
for(c=0,j=len-1;j>=0;j--)//除5
c=c*10+a[j],a[j]=c/5,c%=5;
}
return ans;
}
int main()
{
char s[200];
while(~scanf("%s",s))
{
printf("%d\n",calc(s));
}
}
最後更新：2017-04-02 00:06:57