【競技プログラミング】AtCoder Beginner Contest 148_E問題

# 問題
https://atcoder.jp/contests/abc148/tasks/abc148_e

## 要約
1. 関数f(n)の定義
   - n < 2 のとき、f(n) = 1
   - n ≥ 2 のとき、f(n) = n * f(n-2)

2. 変数
   - N: 与えられる整数

3. 求めるもの
   f(N)を10進法で表記したときに、末尾に連続して現れる0の個数


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順

f(N)の末尾の0の個数を効率的に求めるために、直接f(N)を計算するのではなく、数学的な性質を利用する。
末尾の0の個数は、その数の素因数に含まれる2と5の対の数に等しい。
f(N)の定義から、2の因子は常に十分にあるため、5の因子の数が重要になります。

1. 入力されたNが奇数の場合、f(N)は必ず奇数になるため、末尾の0の個数は0となる。
   この場合、即座に0を出力して終了する。

2. Nが偶数の場合、f(N)に含まれる5の因子の数を数える必要がある。

3. f(N)の5の因子の数を効率的に数えるために、Nを2で割った値（N//2）を新たなNとして扱う。
   これは、f(N)の計算過程で偶数の項のみが5の因子を提供するためである。

4. 新たなNに対して、以下の操作を繰り返す：
   a. N を 5 で割った商（N//5）を答えに加算する。
      これは、現在のNまでの数に含まれる5の因子の数を表す。
   b. N を 5 で割った商で更新する（N = N//5）。
      これは、25, 125, ...といった5の累乗の寄与を考慮するためである。

5. N が 0 になるまで上記の操作を繰り返し、最終的な答えを出力する。


# ACコード
```python:ac.py
def io_func():
    # 標準入力からNを整数として読み込む
    N = int(input())
    return N

def solve(N):
    # Nが奇数の場合、末尾の0の個数は0
    if N % 2 == 1:
        print(0)
        return

    # 末尾の0の個数（5の因子の数）を格納する変数
    zero_count = 0

    # Nを2で割る（偶数の項のみが5の因子を提供するため）
    N //= 2

    # Nが0になるまでループ
    while N:
        # 現在のNまでの数に含まれる5の因子の数を加算
        zero_count += N // 5
        # Nを5で割って更新（5の累乗の寄与を考慮）
        N //= 5

    # 最終的な末尾の0の個数を出力
    print(zero_count)

# メイン処理
N = io_func()
solve(N)

###
# N: 入力された整数値
# zero_count: f(N)の末尾の0の個数（5の因子の数）

# 1. io_func関数で標準入力からNを読み込む
# 2. solve関数でf(N)の末尾の0の個数を計算する
#    2.1 Nが奇数の場合、即座に0を出力して終了
#    2.2 Nが偶数の場合、以下の処理を行う
#        - Nを2で割る
#        - Nが0になるまで以下を繰り返す
#          * N//5を答えに加算
#          * Nを5で割る
#    2.3 最終的な答えを出力する
# 3. メイン処理でio_func関数とsolve関数を呼び出す
```

## オブジェクト指向版1
```python:ac.py
from abc import ABC, abstractmethod

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        # 標準入力からNを整数として読み込む
        return int(input())

class ZeroCounter(ABC):
    @abstractmethod
    def count_zeros(self, n):
        pass

class FactorialZeroCounter(ZeroCounter):
    def count_zeros(self, n):
        # Nが奇数の場合、末尾の0の個数は0
        if n % 2 == 1:
            return 0

        # 末尾の0の個数（5の因子の数）を格納する変数
        zero_count = 0

        # Nを2で割る（偶数の項のみが5の因子を提供するため）
        n //= 2

        # Nが0になるまでループ
        while n:
            # 現在のNまでの数に含まれる5の因子の数を加算
            zero_count += n // 5
            # Nを5で割って更新（5の累乗の寄与を考慮）
            n //= 5

        return zero_count

class ResultPrinter(ABC):
    @abstractmethod
    def print_result(self, result):
        pass

class ConsoleResultPrinter(ResultPrinter):
    def print_result(self, result):
        # 結果を標準出力に出力
        print(result)

class FactorialZeroCounterApp:
    def __init__(self, input_reader: InputReader, zero_counter: ZeroCounter, result_printer: ResultPrinter):
        self.input_reader = input_reader
        self.zero_counter = zero_counter
        self.result_printer = result_printer

    def run(self):
        # 入力を読み込む
        n = self.input_reader.read_input()
        # 0の個数を計算
        result = self.zero_counter.count_zeros(n)
        # 結果を出力
        self.result_printer.print_result(result)

# メイン処理
if __name__ == "__main__":
    input_reader = ConsoleInputReader()
    zero_counter = FactorialZeroCounter()
    result_printer = ConsoleResultPrinter()
    
    app = FactorialZeroCounterApp(input_reader, zero_counter, result_printer)
    app.run()

###
# n: 入力された整数値
# zero_count: f(N)の末尾の0の個数（5の因子の数）

# InputReader: 入力を読み込むための抽象基底クラス
# ConsoleInputReader: 標準入力から整数を読み込むクラス
# ZeroCounter: 0の個数を数えるための抽象基底クラス
# FactorialZeroCounter: 階乗の末尾の0の個数を数えるクラス
# ResultPrinter: 結果を出力するための抽象基底クラス
# ConsoleResultPrinter: 結果を標準出力に出力するクラス
# FactorialZeroCounterApp: アプリケーションのメインロジックを含むクラス

```

### オブジェクト指向で書くメリット
#### 1. 高い拡張性と柔軟性
現在のコードはコンソールからの入力と出力を扱っていますが、将来的にファイルからの入力や、データベースへの出力に変更したい場合、新しいクラスを追加するだけで対応できます。

```python:ac_object.py
class FileInputReader(InputReader):
    def read_input(self):
        with open('input.txt', 'r') as f:
            return int(f.read().strip())

class DatabaseResultPrinter(ResultPrinter):
    def print_result(self, result):
        # データベースに結果を保存する処理
        pass

# 使用例
app = FactorialZeroCounterApp(FileInputReader(), zero_counter, DatabaseResultPrinter())

```

#### 2. テストの容易さ
ZeroCounterクラスのテストを書く場合、入力や出力の処理を気にせずにロジックのみをテストできます。

```python:ac_object.py
import unittest

class TestFactorialZeroCounter(unittest.TestCase):
    def setUp(self):
        self.counter = FactorialZeroCounter()

    def test_count_zeros(self):
        self.assertEqual(self.counter.count_zeros(5), 1)
        self.assertEqual(self.counter.count_zeros(10), 2)
        self.assertEqual(self.counter.count_zeros(25), 6)
        self.assertEqual(self.counter.count_zeros(125), 31)

```



#### 3. 関心の分離
アルゴリズムの変更が必要な場合、FactorialZeroCounterクラスのみを修正すれば良く、入力や出力の処理を変更する必要はありません。

```python:ac_object.py
class OptimizedFactorialZeroCounter(ZeroCounter):
    def count_zeros(self, n):
        # より効率的なアルゴリズムを実装
        pass

# 使用例
app = FactorialZeroCounterApp(input_reader, OptimizedFactorialZeroCounter(), result_printer)


```

#### 4. コードの再利用性

InputReaderやResultPrinterのインターフェースは、他の数学的問題を解くアプリケーションでも使用できます。

```python:ac_object.py
class PrimeFactorizationApp:
    def __init__(self, input_reader: InputReader, factorizer: Factorizer, result_printer: ResultPrinter):
        self.input_reader = input_reader
        self.factorizer = factorizer
        self.result_printer = result_printer

    def run(self):
        n = self.input_reader.read_input()
        result = self.factorizer.factorize(n)
        self.result_printer.print_result(result)

```