数据和题解有误
查看原帖
数据和题解有误
496840
SAMSHAWCRAFT楼主2024/3/8 18:02

本题 E 题首先要求了完美平方数本身是一个完全平方数,而题解和数据的答案都是 14994410401499441040, 注意到该答案最后两位为 4040,因此该数字不可能为一个完全平方数,自然也不可能是一个完美平方数。

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

{-# 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 ()
  
2024/3/8 18:02
加载中...