PKU 2140 Herd Sums
問題文→ 2140 -- Herd Sums
[問題]
自然数Nが与えられる。 Nを連続した自然数の和で表すと何通りできるか。
(例)
N = 15
[7+8 , 4+5+6 , 1+2+3+4+5 , 15] 4通り
Sum(b) - Sum(a-1) = Sum([a,b]) みたいなことすると O(n^2)とかになって間に合わない。
なので
S(m,n) = Sum([m , m + n]) = N を満たす m,nを直接求める方針にする。
S(m,n) = 1/2(2m+n)(n+1) = N になるので、任意のnに対して mが一意に決まる。 これで間に合った。
int main(){ int N; cin>>N; int res = 0; for(int n = 0; n+1 <= N; n++) { if(2*N % (n+1) == 0){ int t = 2*N / (n+1) - n; if(t > 0 && t%2==0) res++; } } cout<<res<<endl; }