2001 - CÙNG MỘT TÍCH(DÀNH CHO HỌC SINH THCS VÀ THPT)(DÀNH CHO H...

Bài 84/2001 - Cùng một tích

(Dành cho học sinh THCS và THPT)

Thuật toán: Gọi số lượng số xi =1 là a, số lượng số xi=-1 là b, số lượng số xi = 0 là c. Ta có: a+b+c=N.

Với mỗi giá trị c khác nhau ta có tương ứng một nghiệm. Nên số nghiệm bằng số giá trị mà c có thể nhận

được. Nếu duyệt theo biến c thì có rất nhiều khả năng nên thay vì duyệt theo biến c ta duyệt theo a và b. Vai

trò của các số bằng 1 và các số bằng -1 là như nhau nên ta có thể giả sử số lượng số bằng 1 lớn hơn số lượng

bằng -1 (a>=b).

Vậy xi = a-b và xi

= a+b (i = 1,..,N)

xixj = P (i =1, ..., N; j =1, ..., N; i<>j) suy ra P =2*xixj (i =1, ..., N -1; j =1, ..., N; i<j)

Ta có phương trình: (a+b)+p=(a-b)

suy ra 0 <= (a-b) <= sqrt(a+b+p) <= sqrt(N+p)<[sqrt(2*10

)] = 44721.

Vậy ứng với mỗi giá trị (a-b) ta có một giá trị (a+b) và một giá trị c. Lần lượt thử với từng giá trị của (a-b)

rồi kiểm tra xem a, b và c thoả mãn các tính chất không?

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}

{$M 16384,0,655360}

uses crt;

const fi ='input.txt';

fo ='output.txt';

var n,p, h :longint;

dem :longint;

t :real;

procedure docf;

var f :text;

begin

assign(f,fi);

reset(f);

read(f,n,p);

close(f);

dem:=0;

end;

procedure lam;

var can :longint;

can:=trunc(sqrt(2*n));

for h:=0 to can do

begin

t:=h;

t:=sqr(t)-p;

if (t>=h)and(t<=n) then inc(dem);

end;

procedure ghif;

assign(f,fo);

rewrite(f);

writeln(f,dem);

close(f);

BEGIN

docf;

if p mod 2=0 then lam;

ghif;

END.