思路
数学题
首先列出等差数列求和的式子。
[S = frac{(n + m)(n - m + 1)}{2}(n为末项，m为首项)
]
[S * 2= (n + m)(n - m + 1)
]
若想让m更小，那么肯定要让等差数列中数字的数目更多。也就是让((n - m + 1))更大，而((n - m + 1))肯定是(S * 2)的因子。所以枚举一下((n - m + 1))
假设((n - m + 1) = x) 则(n = x + m - 1)。然后前面那一项就变成了(x + m - 1 + m)也就是(2 * m - 1 + x)。
然后前一项也可以通过(frac{S * 2}{x})得到。这样就可以得到$$2 * m - 1 + x = frac{S * 2}{x}$$$$m = frac{S * 2 - x + 1}{2}$$，只要保证，m是正整数就行了。
复杂度就是枚举S * 2的因子x的复杂度。因为后面的都可以用最后这个式子进行O(1)计算。
代码
/*
* @Author: wxyww
* @Date: 2018-12-10 08:36:41
* @Last Modified time: 2018-12-10 08:40:48
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int main() {
ll s = read() * 2;
for(ll x = sqrt(s);x >= 1;--x) {
if(s % x) continue;
ll m = (s / x + 1 - x);
if(m & 1) continue;
cout<<m / 2 <<" "<< m / 2 - 1 + x;
return 0;
}
return 0;
}
一言
萤火之光看起来比平常要更耀眼是错觉吗？今宵会成为永夜的吧。