数据和题解有误

本题 E 题首先要求了完美平方数本身是一个完全平方数，而题解和数据的答案都是

1499441040

，注意到该答案最后两位为

40

，因此该数字不可能为一个完全平方数，自然也不可能是一个完美平方数。

因此，本题的所有题解都没有正确求解 E 题，而本题的数据也是错误的。下面贴一份 Haskell 代码，可以求出前 2020 项完美平方数并输出。我这里面用了些数论优化，只考虑个位数，按理说这个代码可以接着做更多位的数据优化，但是不太必要了。

HASKELL

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE Strict, MultiParamTypeClasses, FlexibleInstances #-}
import Control.Monad
import System.IO

square :: Integer -> Integer
square x = x * x

-- 0 ^ 2 = 0, 1 ^ 2 = 1, 2 ^ 2 = 4, 3 ^ 2 = 9, 4 ^ 2 = 6 
-- 5 ^ 2 = 5, 6 ^ 2 = 6, 7 ^ 2 = 9, 8 ^ 2 = 4, 9 ^ 2 = 1
-- if x mod 10 = 3 then the next candidate is some y mod 10 = 7
succCandidate :: Integer -> Integer
succCandidate x 
 | mod x 10 == 3 = x + 4
 | otherwise = x + 1

checkDigit :: Integer -> Bool
checkDigit x
 | x >= 10 = checkDigit (div x 10) && checkSingleDigit (mod x 10)
 | otherwise = checkSingleDigit x
 where
  checkSingleDigit :: Integer -> Bool
  checkSingleDigit x
   | x == 0 || x == 1 || x == 4 || x == 9 = True
   | otherwise = False

replicateTransitionM :: Monad m => Int -> a -> (a -> Bool) -> (a -> m a) -> m a
replicateTransitionM 0 x _ _ = return x
replicateTransitionM n x g f
 | g x = f x >>= \y -> replicateTransitionM (n - 1) y g f
 | otherwise = f x >>= \y -> replicateTransitionM n y g f

main :: IO ()
main = do
  replicateTransitionM 2020 0 (checkDigit . square) $ \x -> do
    when ((checkDigit . square) x) (print (x * x)) >> return (succCandidate x)
  >> return ()

讨论操作

回复

相关推荐

数据和题解有误