题目：

loneliness 是一位奇怪的人，他喜欢在众多看似没有规律的自然数中找寻自己的规律。这一天，他突然想要知道对于给定的一个整数 n，有多少由整数组成，公差为 1 且和为 n 的等差序列，但因为 loneliness 太过于奇怪导致其他人对他的问题以及不再想涉及，所以你能帮帮他找到有多少个这样的序列吗。

输入描述:

输入一个整数 n (1 <= n <= )。

输出描述:

输出一个整数，表示和为 n 的公差是 1 的序列的数量。

(运行时间限制为1秒)

题解：

为了方便讨论数学问题，下面的讨论中，统一把题目输入的n叫做！！！

由题意，其本质是搜索有多少组连续整数和为

不难证明，对于任意的连续正整数序列，存在且仅存在一个包含非正数的序列的和与之相等。

比如说：，，

所以说我们只需要计算连续正整数序列有多少个，然后结果乘2就是答案

如果直接使用简单的双指针定义首项和末项，然后动态缩减边界求和判断是否符合条件，那么这种方法需要执行次判断才能完成，而题目是输入的达到级别，也就是得执行次，而计算机一秒钟最多执行~次，显然不行，需要用数学方法优化。

连续正整数之和就是公差是1的等差数列，等差数列前n项和公式：

变形得：

因为公差是1，那么，则：

设，则：

我们可以取遍每一种可能的项数n

先确定n的取值范围，也就是我们的连续正整数序列可能的长度

易得：n最小为1，也就是的情况

当n取最大时，那么要取最小，这样子项数n才会最大

最小为1，则

也就是说，n一定小于

所以说我们只需要枚举n为范围即可，取根号为左右，因此这种方法不会超时

接下来我们需要讨论取到的n是否有对应的有效，如果n能取到对应的正整数，就说明找到了一组序列

对变形得，仅需为整数就说明找到了一组

同时我们也知道了，对于一个有效的n来说，是唯一的，不存在一个n下有多个皆可的情况，此方程有唯一解

所以说程序仅需实现：n取遍并且判断是否为偶数

不过有一点需要注意，是整数除法，小数点会被忽略，所以说我们还需要额外的判断才行

具有数学意义，必定为整数，所以说合法的是必定为整数，如果出现小数就说明n不符合条件

因此最终版本的算法如下：

  1. n取遍

  2. 判断t能否被整除 并且 是否为偶数，如果符合条件，那么就找到了一组有效的，计次+1

  3. 最终的计次结果乘2就是答案

我们可以写出测试代码看看效果：

#include  <bits/stdc++.h>
using namespace std;
using ll  =  long long;

void solve(ll sn) {
	ll t  =  2  *  sn;
	ll sqrtt  =  sqrt(t);
	for (ll n  =  1;  n  <=  sqrtt;  n++) {
		ll l,  r;
		if (t  %  n  ==  0) {
			l  =  (t  /  n  +  1  -  n);
			if (l  %  2  ==  0) {
				l  /=  2;
				r  =  l  +  n  -  1;
				cout  <<  "l:"  <<  l  <<  " r:"  <<  r  <<  "\n";
			}
		}
	}
}

int main() {
	ll n;
	cin  >>  n;
	solve(n);
	return 0;
}

输入42测试，运行结果如下：

l:42 r:42
l:13 r:15
l:9 r:12
l:3 r:9

输入测试，运行结果如下(运行时间<10ms)：

l:1000000000000 r:1000000000000
l:199999999998 r:200000000002
l:39999999988 r:40000000012
l:7999999938 r:8000000062
l:1599999688 r:1600000312
l:319998438 r:320001562
l:122066217 r:122074408
l:63992188 r:64007812
l:24393583 r:24434542
l:12760938 r:12839062
l:4780413 r:4985212
l:2364688 r:2755312
l:464563 r:1488562

没有任何问题。

因此，可以采用本算法，下面是可以AC的代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll solve(ll sn) {
	ll t = 2 * sn;
	ll sqrtt = sqrt(t);
	ll ans = 0;
	for (ll n = 1; n <= sqrtt; n++) {
		if (t % n == 0 && (t / n + 1 - n) % 2 == 0) {
			++ans;
		}
	}
	ans *= 2;
	return ans;
}

int main() {
	ll n;
	cin >> n;
	cout << solve(n);
	return 0;
}

测试结果：

答案正确
通过全部用例
运行时间 531ms
占用内存 464KB