COUNTCBG – spoj

Đề bài:

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:

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.
Khuyên dùng

 

Speak Your Mind

*