当前位置：首页 > news >正文

【蓝桥杯】可分解的正整数

news 来源：原创 2025/7/5 8:37:29

可分解的正整数

定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件：

序列长度至少为 3。
序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整数、负整数或 0。

例如，[1,2,3]、[4,5,6,7] 和 [−1,0,1] 是符合条件的序列，而 [1,2]（长度不足）和[1,2,4]（不连续）不符合要求。

现给定一组包含 N 个正整数的数据 A1,A2,…,AN。

如果某个 Ai 能够表示为符合上述条件的连续整数序列中所有元素的和，则称 Ai 是可分解的。

请你统计这组数据中可分解的正整数的数量。

输入格式

输入的第一行包含一个正整数 N，表示数据的个数。

第二行包含 N 个正整数 A1,A2,…,AN，表示需要判断是否可分解的正整数序列。

输出格式

输出一个整数，表示给定数据中可分解的正整数的数量。

数据范围

对于 30% 的评测用例，1≤N≤100，1≤Ai≤100。
对于 100% 的评测用例，1≤N≤ $10^5$ ，1≤Ai≤ $10^9$ 。

输入样例：

3
3 6 15

输出样例：

样例解释

Ai=3 是可分解的，因为 [0,1,2] 的和为 0+1+2=3。

Ai=6 是可分解的，因为 [1,2,3] 的和为 1+2+3=6。

Ai=15 是可分解的，因为 [4,5,6] 的和为 4+5+6=15。

所以可分解的正整数的数量为 3。

【思路分析】

这一题看起来似乎比之前的蓝桥杯中的一道题《数字诗意》还要复杂，实则不然

P10900 [蓝桥杯 2024 省 C] 数字诗意

数字诗意题解

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

先说结论，这个题中只要是大于1的正整数都能够分解成序列长度至少为3，可以包含正整数，负整数或者0的连续递增序列

因为可以包含负整数，所以可以以0为分界线，0右边的数可以被左边的数抵消，但是因为1只能由[0,1]组成，所以1不符合题意

Ai=2时，-1 0 1 2，-1把1抵消掉了，序列长度满足要求

Ai=3时，-2 -1 0 1 2 3，-2 -1把1 2抵消掉了，序列长度满足要求

以此类推，Ai=m时，只要-(m - 1) ,-(m- 2) … -1把1 2 … m - 1抵消掉即可

import java.io.*;
import java.util.*;
public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] data = br.readLine().split(" ");int res = 0;for(int i = 0; i < n; i++) {int a = Integer.parseInt(data[i]);if(a > 1) {res++;}}System.out.println(res);br.close();}
}