uva 568 - Just the Facts

ps:重新看了一下题目，发现zoj的n没限制。。。而uva跟poj却限制到10000以内，所以前一个做法的预处理不一定够大，还是第二个方法强悍啊

不得不说，因为这题，我知道了poj的数据很水。。zoj这题过不了，uva却过了。

//不懂，觉得大数会超时，上网搜，题解
//f(i)=f(i-1)*i%10,i%5=0;
//f(i)=mod(2,(n-1)%4+1))*f(n)%10,i%5!=0,n=i/5;
//mod(2,(n-1)%4+1))的取值范围是2,4,6,8
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string>
using namespace std;
//#define TEST
long a[10001]={0, 1, 2, 6, 4, 2},b[5]={0, 2, 4, 8, 6};
int main() {
#ifdef TEST
	freopen("input.txt", "r", stdin);
#endif
	long m , n;
	for(long i = 6; i <= 10000; i++){
		m = i % 5;
		n = i / 5;
		if(m != 0) a[i] = a[i - 1] * i % 10;
		else a[i] = b[(n - 1) % 4 + 1] * a[n] % 10;
	}
	while(cin >> n) {
		printf("%5d -> %d/n", n, a[n]);
	}
	return 0;
}

后来看数论模版看到了一个方法：

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstring>
using namespace std;
int lastdigit(char*buf)
{
   const int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
   int len=strlen(buf),a[110],i,c,ret=1;
   if(len==1)
      return mod[buf[0]-'0'];
   for(i=0;i<len;i++)
      a[i]=buf[len-1-i]-'0';
   for(;len;len-=!a[len-1])
   {
      ret=ret*mod[a[1]%2*10+a[0]]%5;
      for(c=0,i=len-1;i>=0;i--)
         c=c*10+a[i],a[i]=c/5,c%=5;
   }
   return ret+ret%2*5;
}
int main() {
	char s[10];
	while(cin >> s) {
		printf("%5s -> %d/n", s, lastdigit(s));
	}
	return 0;
}