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

Problem 29

この問題は、本当は素因数分解などする必要はありません。99 * 99 = 9801通りの中で重複する数を削ればいいのです。重複するのは例えば、2⁴ = 4²です。このようになるのは、少なくとも片方が2乗以上のべき乗数です。このような数を指数ごとに数えます。例えば、2乗数は2², 3², ..., 10²とありますが、4² = 2⁴なのでこの場合は大きな指数にします。そうすると、重複の数は指数で決まってくるので、この数をさっき数えた数で掛けて、9801から引けば答えが出てきます。

@echo off

setlocal enabledelayedexpansion
set /a N = 100
call :calc_pows %N%
set /a s = (%N% - 1) * (%N% - 1)
for /L %%e in (2, 1, %max_e%) do (
    call :calc_overlap %%e
    set /a s -= !ERRORLEVEL! * "pows_%%e"
)
echo %s%
exit /b 0

:calc_pows
    call :calc_max_e %N%
    set /a max_e = %ERRORLEVEL%
    for /L %%e in (2, 1, %max_e%) do (
        call :calc_max_base %N% %%e
        for /L %%m in (2, 1, !ERRORLEVEL!) do (
            call :pow %%m %%e
            set /a dic_!ERRORLEVEL! = %%e
        )
    )
    
    for /L %%e in (2, 1, %max_e%) do set /a pows_%%e = 0
    for /F "usebackq delims=_= tokens=3" %%e in (`set dic_`) do (
        set /a pows_%%e += 1
    )
    exit /b 0

:calc_overlap
    setlocal
    for /L %%k in (0, 1, %N%) do set /a a_%%k = 0
    set /a e_1 = %1 - 1
    for /L %%e in (1, 1, %e_1%) do (
        call :gcd %%e %1
        set /a d = %1 / !ERRORLEVEL!
        for /L %%f in (!d!, !d!, %N%) do (
            set /a k = %%e * %%f / %1
            set /a a_!k! = 1
        )
    )
    
    set /a s = 0
    for /L %%k in (2, 1, %N%) do set /a s += "a_%%k"
    exit /b %s%

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

:gcd
    setlocal
    if %2 == 0 exit /b %1
    set /a r = %1 %% %2
    call :gcd %2 %r%
    exit /b %ERRORLEVEL%

rem // max e s.t. 2^e <= N
:calc_max_e
    setlocal
    if %1 == 1 exit /b 0
    set /a n = %1 / 2
    call :calc_max_e %n%
    set /a r = 1 + %ERRORLEVEL%
    exit /b %r%

rem // max m s.t. m^e <= N
:calc_max_base
    setlocal
    set /a m = 2
    :loop_calc_max_base
        call :pow %m% %2
        if %ERRORLEVEL% LEQ %1 (
            set /a m += 1
            goto :loop_calc_max_base
        )
    set /a m -= 1
    exit /b %m%