#UVa:568-Just the Facts

循序從1~10000一直乘上去,由於最大值是到10000,因此每次計算完留下結尾非零的五位數再去做乘法,即可得到正確的最後一位非零數字。

循序從 1 到 10000 一直乘上去,雖然最大值是到 10000 ,但無法在每次計算完僅留結尾,因為這個乘法去零的動作其實隱性的位數有再一直提升,所以前面截掉的部分到越後面就越有可能影響,所以最後就是利用大數乘法先乘完後,將答案都先記下來後,再輸出它要的答案即可。

C++(0.110)

/*******************************************************/
/* UVa 568 Just the Facts                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/03/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int dp[10005] = {1, 1};
  int num[10000] = {1};
  int minDigit = 0;
  int maxDigit = 1;

  for(int i = 2 ; i <= 10000 ; ++i){
    for(int j = minDigit ; j < maxDigit ; ++j){
      num[j] *= i;
    }

    for(int j = minDigit ; j < maxDigit || num[j] >= 10000 ; ++j){
      num[j+1] += num[j] / 10000;
      num[j] %= 10000;
    }

    while(num[minDigit] == 0) ++minDigit;
    while(num[maxDigit] != 0) ++maxDigit;

    int digit = num[minDigit];
    while(digit % 10 == 0) digit /= 10;
    dp[i] = digit % 10;
  }

  int N;
  while( scanf("%d", &N) != EOF ){
    printf("%5d -> %d\n", N, dp[N]);
  }
  return 0;
}

2 回應

  • 阿登
    input 9375時會錯誤喔 output應該是8 不是3
    • 修正了,感謝告知! m(_ _)m (雖然有點長沒有上來 Blog 所以隔了很久 Orz......)

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: