COUNTCBG – spoj

Đề bài:

• http://vn.spoj.com/problems/COUNTCBG/

Thuật toán:

• Ta xét tổng các số từ l -> r thì ta cần tìm l , r sao cho :l + (l+1) + … + (r-1) + r = n

  ⇒ (r+l)(r-l+1)/2 = n

  ⇒ (l+r)(r-l+1) = 2n

  Giải phương trình nghiệm nguyên đơn giản này

  Ta xét phần (l+r). Đương nhiên l + r >= 2 vì l >= 1, r >= l;

  Do l <= r nên ta chỉ cần xét (l + r) từ 2 -> sqrt(2n) thôi vì phần còn lại sẽ tạo ra bộ nghiệm tương tự phần ta xét

  Cho i = 2 -> sqrt(2n) :

  Nếu (2n) chia hết cho i thì ta bắt đầu :

  l + r = i và r – l + 1 = 2n/i hay r – l = 2n/i -1

  ⇒ 2r = i + 2n/i -1 mà r nguyên

  ⇒ (i + 2n/i – 1) chẵn

  ⇒ l cũng nguyên do r nguyên

  Vậy điều kiện để có một nghiệm cho bài toán là

  (2n) chia hết cho i và (i + 2n / i – 1) chẵn

  Nhận xét thời gian thực thi thuật toán là :

  O(100*sqrt(2*10^9))

Code:

• (xem code)

Program COUNTCBG;
Var
  n,res :LongInt;

  procedure Solve;
  var
    i :LongInt;
  begin
    res:=0;
    for i:=2 to Trunc(Sqrt(2*n)) do
      if (2*n mod i=0) then
        if ((i+2*n div i-1) mod 2=0) then Inc(res);
  end;

Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  while not EoF do
    begin
      ReadLn(n);
      Solve;
      WriteLn(res);
    end;
  Close(Input); Close(Output);
End.