Editorial for Bedao Regular Contest 01 - EXP


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Dễ thấy vì ~X~ và ~Y~ đều là các số thuộc đoạn ~[0,10^{18}]~ nên ta có thể dùng hàm pow của C++ để tính nhưng làm như vậy thì độ phức tạp rất lớn. Ta có thể giảm độ phức tạp bằng cách so sánh các số mũ của ~10~ ( lấy các B của X và Y so sánh )

  • Nếu ~Bx > By~ thì ta có ~Bx = Bx - By~ và ~By = 0~.
  • Nếu ~Bx < By~ thì ta có ~Bx = 0~ và ~By = By - Bx~.
  • Nếu ~Bx = By~ thì ta có ~Bx = 0~ và ~By = 0~ thì ta chỉ cần so sánh Ax * pow(10,Bx) và Ay * pow(10,By) vì ~Bx~ và ~By~ đều được giảm nên độ phức tạp không còn quá lớn.

Lưu ý: Ta phải xử lý trường hợp số ~A~ của ~X~ hoặc ~Y = 0~ vì khi ta nhân cho ~0~ thì số đó luôn là số bé nhất


Comments

Please read the guidelines before commenting.


There are no comments at the moment.