バッチファイルでProject Euler（69）

Problem 30

もうちょっと速くならないでしょうか。下の桁から考えて枝刈りすることを考えましょう。例えば、4乗で考えて632とすると、べき乗和は6⁴+3⁴+2⁴=1393となります。元の数との差は761です。次に千の位に数字をつけます。例えば9なら元の数は9000増えてべき乗和は9⁴=6561増えます。0が来ないかぎり元の数の増分のほうが大きいです。その差が一番小さくなるのは1のときで、元の数は1000増えてべき乗和は1増えます。この場合、999-761=238で、元の数のほうが大きくなります。この先も何桁追加しても元の数の増分が大きくなります。だから632の左にいくら数字を付け足しても元の数とべき乗和は同じになりません。
このようにして枝刈りすると、5乗で14分になりました。

@echo off

setlocal enabledelayedexpansion
set /a N = 5
call :calc_pows pows %N%
call :calc_max_num_digits
set /a max_num_digits = %ERRORLEVEL%
call :calc_inc inc
set /a max_num_digits_1 = %max_num_digits% - 1
for /L %%m in (0, 1, %max_num_digits_1%) do (
    call :calc_min inc_%%m
    set /a inc_min_%%m = !ERRORLEVEL!
)
call :sum_f 0 0 1 1
echo %ERRORLEVEL%
exit /b 0

:calc_pows
    for /L %%d in (0, 1, 9) do (
        call :pow %%d %2
        set /a %1_%%d = !ERRORLEVEL!
    )
    exit /b 0

:calc_max_num_digits
    setlocal
    set /a e = 0
    set /a mm = 0
    :loop_calc_max_n
        set /a m = n * %pows_9%
        set /a mm = %mm% * 10 + 9
        set /a e += 1
        if %m% LSS %mm% exit /b %e%
        goto :loop_calc_max_n

:calc_inc
    set /a dec = 1
    for /L %%m in (1, 1, %max_num_digits%) do (
        for /L %%d in (0, 1, 9) do (
            set /a %1_%%m_%%d = %%d * !dec! - "pows_%%d"
        )
        set /a dec *= 10
    )
    exit /b 0

:calc_min
    setlocal
    set /a m = "%1_1"
    for /L %%m in (2, 1, 9) do (
        set /a mm = "%1_%%m"
        if !mm! LSS !m! set /a m = !mm!
    )
    exit /b %m%

:sum_f
    setlocal
    set /a n0 = %1
    set /a diff0 = %2
    set /a m = %3
    set /a dec0 = %4
    
    if %m% GTR %max_num_digits% exit /b 0
    set /a m_1 = %m% - 1
    set /a m__1 = %m% + 1
    set /a dec = %dec0% * 10
    set /a inc_min_next = "inc_min_%m%"
    if %inc_min_next% GTR 0 (
        set /a diff = %diff0% + "inc_min_%m_1%"
        if !diff! GTR 0 exit /b 0
    )
    
    set /a s = 0
    for /L %%d in (0, 1, 9) do (
        set /a n = %n0% + %%d * %dec0%
        set /a diff = %diff0% + !n! - %n0% - "pows_%%d"
        if !diff! == 0 (
            if %%d GTR 0 (
                if !n! GTR 1 set /a s += !n!
            )
        )
        
        set /a b = 0
        if !diff! LEQ 0 set /a b = 1
        set /a diff2 = !diff! + "inc_%m_1%_%%d"
        if !diff! LEQ 0 set /a b = 1
        if !b! == 1 (
            call :sum_f !n! !diff! %m__1% %dec%
            set /a s += !ERRORLEVEL!
        )
    )
    exit /b %s%

:pow
    setlocal
    set /a p = 1
    for /L %%e in (1, 1, %2) do set /a p *= %1
    exit /b %p%