Блог пользователя Los_Angelos_Laycurse

Автор Los_Angelos_Laycurse, 10 лет назад, По-английски

Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=4010

It involves to solve bivariate polynomial equation with degree k:(find all solution in a interval[left,right].) i.e.

sigma(A[i][j]*u1^i*u2^j)==0  

  sigma(B[i][j]*u1*i*u2^j)==0  

  (i<=k[0],j<=k[1])  k[0],k[1]<=5,(u1,u2 are veriables)

I haved tried to eliminate the veriable u1: we can write the equation as

f(u1,u2)==sigma(Fi(u2)*u1^i)==0  

              g(u1,u2)==sigma(Gi(u2)*u1^i)==0

              Fi(u2),Gi(u2) are polynomials of u2

first we can eliminate u1^k[0] , f'(u1,u2)==g(u1,u2)*Fk[0]-f(u1,u2)*Gk[0]

g'(u1,u2)== f'(u1,u2)*u1*Gk[0]-g(u1,u2)*Fk[0]-1 .

if we use this approach we can finally get a one veriable polynomial equation F(u2)==0,but the degree is two high, about hundred magnitude we can prove upperbound is about 10th fibonacci number multiply 5 ,this is also a big problem to solve F(u2)==0. I have tried find derive of F(u2) and solve F'(u2)==0 to find extreme point of F(u2) and binary search with each segment.but WA 6s,because of precision error(miss some solution) maybe we can find one of the solution and divide the polynomial?? but how to find one solution without too much precision error?? this is also a big problem....

is there anybody have better idea?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится