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;
}