正经解题思路但是没AK(怒

原题链接：29433.智慧数
userId_undefined

Erika

秩序白银

2024-10-26 16:34:37

发布于：湖南

24阅读
0回复
0点赞

这个智慧数的定义不难发现其实就是两个完全平方数的差
然后要我们找在区间[1,n][1, n]内所有不合法(如上条件)的数
比如一个数xx是智慧数，当且仅当存在两个整数aa和bb使得 x=a2−b2x = a^2 - b^2
如果你在初一的时候也学习了平方差公式，那么你可以知道 a2−b2=(a−b)(a+b)a^2 - b^2 = (a - b)(a + b)
所以xx必须是两个整数的乘积
然后可以遍历所有可能的aa和bb来生成所有可能的智慧数，直到 a2−b2>na^2 - b^2 > n
将生成的智慧数标记出来，剩下的数就是非智慧数
比如在[1,9][1, 9]区间内，智慧数有1,3,4,5,7,8,9，1, 3, 4, 5, 7, 8, 9，其中不是智慧数的数只有22和66

或者：
设k=a2−b2=(a+b)(a−b)k = a^2-b^2=(a + b)(a - b)
当aa，bb为整数时，若aa，bb同奇或同偶，则a+ba+b与a−ba−b均为偶数，所以k=(a+b)(a−b)k=(a + b)(a - b)是4的倍数
若aa，bb一奇一偶，则a+ba+b与a−ba−b均为奇数，所以k=(a+b)(a−b)k=(a+b)(a−b)是奇数
所以智慧数也可以表示为奇数或者4的倍数
非智慧数就是既不是奇数也不是4的倍数的数，也就是形如4k+2(k∈N)4k + 2(k∈N)的数
对于给定的nn，遍历[1,n][1,n]中的每个数ii。
对于每个数ii，判断它是否为智慧数。根据智慧数的规律，可以通过判断ii除以44的余数来确定它是否为智慧数。如果ii是奇数或者ii能被44整除，那么它就是智慧数；如果ii除以44余数为22，那么它就不是智慧数

python code(OLE版))乐了大帅童TM造的什么数据自己都过不了:

n = int(input()) 
n_num = [] 
count = 0 
for i in range(1, n+1): 
    if i%4 == 2: 
        n_num.append(i)  
        count += 1 
print(count) 
for num in n_num: 
    print(num, end=' ')

c++ code(RE版)经测试这题最多最多绿5个点（至少在现在）：

#include <iostream> 
#include <vector> 
using namespace std;
int main() { 
    int n; 
    cin >> n;  
    vector<int> n_num; 
    int count = 0;  
    for (int i = 1; i <= n; ++i) { 
        if (i % 4 == 2) { 
            n_num.push_back(i);  
            count += 1; 
        } 
    }  
    cout << count << endl;  
    for (int num : n_num) { 
        cout << num << " "; 
    }  
    return 0; 
}
userId_undefined
去预览
0/2000

全部评论 1

热门讨论