这个智慧数的定义不难发现其实就是两个完全平方数的差
然后要我们找在区间[1,n][1, n][1,n]内所有不合法(如上条件)的数
比如一个数xxx是智慧数,当且仅当存在两个整数aaa和bbb使得 x=a2−b2x = a^2 - b^2x=a2−b2
如果你在初一的时候也学习了平方差公式,那么你可以知道 a2−b2=(a−b)(a+b)a^2 - b^2 = (a - b)(a + b)a2−b2=(a−b)(a+b)
所以xxx必须是两个整数的乘积
然后可以遍历所有可能的aaa和bbb来生成所有可能的智慧数,直到 a2−b2>na^2 - b^2 > na2−b2>n
将生成的智慧数标记出来,剩下的数就是非智慧数
比如在[1,9][1, 9][1,9]区间内,智慧数有1,3,4,5,7,8,9,1, 3, 4, 5, 7, 8, 9,1,3,4,5,7,8,9,其中不是智慧数的数只有222和666
或者:
设k=a2−b2=(a+b)(a−b)k = a^2-b^2=(a + b)(a - b)k=a2−b2=(a+b)(a−b)
当aaa,bbb为整数时,若aaa,bbb同奇或同偶,则a+ba+ba+b与a−ba−ba−b均为偶数,所以k=(a+b)(a−b)k=(a + b)(a - b)k=(a+b)(a−b)是4的倍数
若aaa,bbb一奇一偶,则a+ba+ba+b与a−ba−ba−b均为奇数,所以k=(a+b)(a−b)k=(a+b)(a−b)k=(a+b)(a−b)是奇数
所以智慧数也可以表示为奇数或者4的倍数
非智慧数就是既不是奇数也不是4的倍数的数,也就是形如4k+2(k∈N)4k + 2(k∈N)4k+2(k∈N)的数
对于给定的nnn,遍历[1,n][1,n][1,n]中的每个数iii。
对于每个数iii,判断它是否为智慧数。根据智慧数的规律,可以通过判断iii除以444的余数来确定它是否为智慧数。如果iii是奇数或者iii能被444整除,那么它就是智慧数;如果iii除以444余数为222,那么它就不是智慧数
python code(OLE版))乐了大帅童TM造的什么数据自己都过不了:
c++ code(RE版)经测试这题最多最多绿5个点(至少在现在):