POH! 7 paizaランクA相当問題「水着」

題目

階乗とは数学の演算の一つで、N の階乗をN! と書きます。N が自然数であるとき、階乗は次のように計算できます。

N! = N * (N - 1) * ... * 2 * 1

N が与えられたとき、N! のすべての桁の代わりに、N! の最下位桁から続く0 をすべて除いた値の下位9桁を求めるプログラムを作成してください。
9桁ではあるが先頭が0であるような場合は先頭の0を取り除いた値を出力してください。先頭に0のついた値を出力すると誤答となります。
例えば N = 38 の時は以下のようになります。

条件

すべてのテストケースにおいて、以下の条件をみたします。
1 ≦ N ≦ 1000000

參考做法(只使用int處理)

#include <iostream>
using namespace st
int main(void){
 // 自分の得意な言語で
 // Let's チャレンジ！！
 string str;
 getline(cin, str);
 int n = atoi( str.c_str() );

 // 先計算 2與5的因數量
 int c2 = 0;
 int c5 = 0;
 for (int i = 2; i <= n; i++) 
 {
  int val = i;
  while (((val % 2) == 0) && val > 1)
  {
   val /= 2;
   c2++;
  }
  while ((val % 5 == 0) && val > 1)
  {
   val /= 5;
   c5++;
  }
 }
 c2 = c5 = c2 > c5 ? c5 : c2;
 int ans = 1;
 for (int i = n; i > 1; i--) 
 {
  int val = i;
  while (c2 > 0 && (val % 2 == 0) && val > 1)
  {
   val /= 2;
   c2--;
  }
  while (c5 > 0 && (val % 5 == 0) && val > 1)
  {
   val /= 5;
   c5--;
  }
  int a1 = (ans / 10000);
  int a2 = (ans % 10000);
  int b1 = (val / 10000);
  int b2 = (val % 10000);
  int ans1 = (((a1 * b1) % 10) ); // * 100000000
  int ans2 = ((((a1 * b2) % 100000) * 10000) + (((a2 * b1) % 100000) * 10000) + (a2 * b2));
  int ans3 = (ans2 / 100000000);
  int ans4 = ans2 - (ans3 * 100000000);
  int ans5 = ((ans1 + ans3) % 10) * 100000000;
  ans = (ans4 + ans5) % 1000000000;
 }
 cout << ans << endl;
 return 0;
}

參考做法2(使用long long處理)

unsigned long long getAxB(unsigned long long a, unsigned long long b)
{
 unsigned long long ans = (a * b);
 while ((ans % 10 == 0) && ans > 1) ans /= 10;
 return ans % 10000000000; // 避免位數不足 這邊多個0
}
int main(void){
 // 自分の得意な言語で
 // Let's チャレンジ！！
 string str;
 getline(cin, str);
 unsigned long long n = atoi( str.c_str() );
 unsigned long long ans = n > 0 ? n : 1;
 for (int i = n - 1; i > 1; i--) ans = getAxB(ans, i);
 ans %= 1000000000;
 cout << ans << endl;
 return 0;
}

參考做法3(使用JS處理)

process.stdin.on('data', function (chunk) {
    var line = chunk.toString();
    var n = parseInt(line);
 function getAxB(a, b)
 {
  var ans = a * b;
  while (ans % 10 == 0 && ans > 1) ans /= 10;
  return ans % 10000000000;
 }
 var ans = 1;
 for (var i = n; i > 1; i--) ans = getAxB(ans, i);
 console.log(ans % 1000000000);
});

感想
題目不難,但 debug環境不太友善,輸出結果不正確不會告訴原因.

因為只需要紀錄9位數,所以直覺感覺可以使用int完成答案,
不過實際上在處理時若只保留9位數,會因消去後位0而有不足位的可能.

ex. N=100327
如果中途計算只保留9位數,最後答案可能為 ans=850809344
但實際的正確答案應為 ans=450809344

所以在只使用int的狀況下,必須要做預處理,先將有可能造成後位0的情況事先排除.

網址
https://paiza.jp/poh/ando?read=true