邯郸做网站最好的公司,网站建设项目规划书社团宣传,营口网站建设求职简历,wordpress小工具最近评论题目描述
传送门——AcWing 3717. 整数序列 - AcWing
很多整数可以由一段连续的正整数序列#xff08;至少两个数#xff09;相加而成#xff0c;比如 2534567121325345671213。
输入一个整数 N#xff0c;输出 N 的全部正整数序列#xff0c;如果没有则输出 NONE。
输…题目描述
传送门——AcWing 3717. 整数序列 - AcWing
很多整数可以由一段连续的正整数序列至少两个数相加而成比如 2534567121325345671213。
输入一个整数 N输出 N 的全部正整数序列如果没有则输出 NONE。
输入格式
一个整数 N。
输出格式 每行输出一个满足条件的整数序列。 序列内部元素从小到大排序。 优先输出首项更小的序列。
数据范围
2 ≤ N ≤ 107
输入样例
25
输出样例
3 4 5 6 7
12 13
思路及代码
二分查找
从 1 ~ n / 2 遍历 i通过二分查找以 i 开头时的答案。
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int N 1e77;
int n;
int main(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);cinn;LL k n / 2;bool tag false;for(LL i1;ik;i){// high k 1作为最大值是因为当最大值大于 n/2时由于要求是一组连续的数所以此时的序列至多有2个数LL low i, high k 1;while(low high){LL mid low high 1 1;if((mid - i 1)*(i mid) 2*n){low mid;}else{high mid -1;}}if((low - i 1)*(i low) 2*n){tag true;for(int ji;jlow;j){coutj ;}cout\n;}}if(tag false){coutNONE;}return 0;
}
数学公式
该题本质考察的是一组连续数的和则令这组连续数的开头是a共k个数那么这组数的和通过求和公式可得为 (a a k - 1) * k / 2。而我们需要求得是 a 和 k当这两个未知数确定后一组数便确定了。
因此考虑 (a a k - 1) * k / 2 n即 (2a k - 1) * k 2n可知由 a 和 k 组成的 y (2a k - 1) 和 x k 两个公式是 2n 的因子。既然如此我们可以去求 2n 的因子考察满足条件的两个因子 x和y由 x和y 可得到 a 和 k。
#includebits/stdc.h
using namespace std;
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n;cin n;n * 2;int cnt 0;// 题目要求优先输出首项更小的序列即 (2a k - 1) * k 中的 a 更小。由 (2a k - 1) * k 2n 可知 k 越大 a越小即因子 x 越大a越小所以这里 x 从大到小遍历 for (int x sqrt(n); x 1; x--) {if (n % x 0) {int y n / x;int t y - (x - 1);// t 2a因此 t 必须是偶数if (t % 2 0) {cnt;int a t / 2;for (int i a; i a x; i) {cout i ;}cout \n;}}}if (cnt 0) {cout NONE;}return 0;
}
