🐕

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

に公開
競技プログラミング
tech

問題

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が与えられたとき、f(N)を10進法で表した際に、末尾に連続する0の個数を求める。

  3. 変数

    • n: 0以上の整数
    • N: 与えられる整数入力値
    • f(n): 定義された関数

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

末尾の0の個数は、f(N)の素因数に含まれる2と5の対の数に等しいことを利用する。
f(N)の定義から、偶数のNに対してのみ0が発生し、その数は主に5の因数の数に依存する。

解法手順

  1. 入力値Nを受け取る。

  2. Nが奇数の場合、末尾の0の個数は常に0なので、0を出力して終了する。

  3. Nが偶数の場合、以下の計算を行う：
    a. 初期値として、N/10の商を答えとする（これは2の因数の寄与）。
    b. Nを10で割った商を新たなNとする。
    c. 5の累乗（5, 25, 125, ...）でNを割り、その商を答えに加算していく。
    d. 5の累乗がNを超えるまでcを繰り返す。

  4. 最終的な答えを出力する。

ACコード

ac.py
def io_func():
    # 入力値Nを受け取る
    N = int(input())
    return N

def solve(N):
    # Nが奇数の場合、末尾の0の個数は常に0
    if N % 2 != 0:
        return 0
    
    # 初期値として、N/10の商を答えとする（2の因数の寄与）
    ans = N // 10
    
    # Nを10で割った商を新たなNとする
    N //= 10
    
    # 5の累乗でNを割り、その商を答えに加算していく
    cnt = 5
    while cnt <= N:
        ans += N // cnt
        cnt *= 5
    
    return ans

if __name__=="__main__":
    # メイン処理
    N = io_func()
    result = solve(N)
    print(result)

###
# N: 入力された整数
# ans: 末尾の0の個数（最終的な答え）
# cnt: 5の累乗（5, 25, 125, ...）

# 1. io_func関数:
#    - 標準入力からNを読み取る
# 2. solve関数:
#    - Nが奇数の場合、0を返す
#    - Nが偶数の場合:
#      a. N/10の商を初期値とする
#      b. Nを10で割る
#      c. 5の累乗でNを割り、商を答えに加算
#      d. 5の累乗がNを超えるまでcを繰り返す
#    - 最終的な答えを返す
# 3. メイン処理:
#    - io_func関数でNを取得
#    - solve関数で結果を計算
#    - 結果を出力

考察

Nが奇数の場合、末尾が0になることはない。

n = 2k+1とする
f(2k+1) = (2k+1) * f(2k-1)
k = 1のとき、f(3)=3f(1)=31=3
k = 2のとき、f(5)=5f(3)=53=15
k = 3のとき、f(7)=7f(5)=715=105
・・・
奇数×奇数は奇数であるため、末尾が0になることはない。

関数f(n)の定義と再帰的な性質

問題文では関数f(n)が再帰的に定義されており、n≥2の場合にf(n) = n*f(n-2)という形式を取っている。
これは、関数の値が偶数の入力に対して急速に大きくなることを示唆している。

末尾の0の個数を求める

問題の目標は、f(N)を10進法で表したときの末尾の0の個数を求めること。
これは、f(N)の因数に含まれる2と5の数に直接関係する。
コードでは、2の因数（N/10の商）と5の因数（5の累乗での除算）を別々に処理している。

2の因数の寄与

Nを偶数としたとき、N/10の商を求めることで、実質的にNから2の因数を1つ取り除いていることになる。
これは、Nに含まれる2の因数の数を1つ減らすことと同じです。
例えば：
N = 240 (= 2^4 × 3 × 5) の場合、N//10 = 24
N = 800 (= 2^5 × 5^2) の場合、N//10 = 80
N = 31000 (= 2^3 × 5^3 × 31) の場合、N//10 = 3100
N//10によって、2×5のペアを一つ見つける。
→あとは、残りの数(3100)に対して、いくつ5の因数を持っているかカウントすればよい。

Discussion