ITSA 52 - [Problem 5] Lowest Non-zero Digit of Factorial - 參考答案

Difficulty: Normal
Ref: ITSA 52 - [Problem 5] Lowest Non-zero Digit of Factorial

/*******************************************************/
/* [Problem 5] Lowest Non-zero Digit of Factorial      */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/21                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int lnzsdf(int x) {
 unsigned i = 0, j, k, l, ret = 1;
 for (k = 282475249, l = 0; k >= 1; l = k, k /= 49)
  for (i -= l, i += k; i <= x; i += k){
   for (j = i; j % 7 == 0; j /= 7);
   ret = (ret * (j % 7)) % 7;
  }
 return ret;
}

int main()
{
 int n;
 scanf("%d", &n);
 while (n--) {
  int N;
  scanf("%d", &N);
  printf("%d\n", lnzsdf(N));
 }
 return 0;
}

Debug： I/O
暴力解會超時，所以就用了點技巧來加速運算。
先投小範圍的測資，例如1~10000，會發現規律，每間格7^(2n)，其中n大於等於0時，會有同樣的循環數產生。
如果題目改為10 base的話，可以參考： Last non-zero digit of a factorial。
網路上有人說可用 Wilson’s Theorem 來解，但我是看不懂啦，只說沒實作，理論大師4ni? 黑人問號...

7
7
14
21
28
2000000000
1234567899
987654321

6
2
1
3
1
2
4