算法小练-可分解的正整数

题目:

蓝桥杯2025省B可分解的正整数

#include<bits/stdc++.h> using namespace std; // 暴力枚举 bool check(int x){ // 枚举等差数列的首项 for(int s = -x; s <= x; s++){ // 枚举等差数列的项数 for(int k = 3; k <= 2 * x + 1; k++){ // 根据等差数列的首项和项数 计算等差数列和 int sum = (s + s + k - 1) * k / 2; if(sum == x){ return true; } } } return false; } int main(){ int n; cin>>n; int ans = 0; for(int i = 1; i <= n; i++){ int x; cin>>x; if(check(x)) ans++; } cout<<ans<<endl; return 0; }

这是暴力枚举法, 容易超时

实则这道题是诈骗题, 仔细分析不难发现只有1不行其他都行