C. Баавгай ба олон гишүүнтүүд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лимак бол жижиг туйлын баавгай. Тэрээр олон тоглоомгүй ба иймд тэрээр ихэнхдээ олон гишүүнтүүдээр тоглодог.

Тэрээр хэрэв олон гишүүнтийн ахмад зэрэг нь $n$ ба коэффициентүүд нь бүхэл тоо бөгөөд абсолют утга нь $k$-аас хэтрэхгүй байвал уг олон гишүүнтийг хүчин төгөлдөр гэж үзнэ. Илүү дэлгэрэнгүйгээр хэлвэл:

$a_{0}, a_{1}, ..., a_{n}$-аар коэффициентүүдийг тэмдэглэе, тэгэхээр болно. Үүний дараа олон гишүүнт $P(x)$ нь хэрэв дараах нөхцөлүүдийг хангаж байвал хүчин төгөлдөр байна:

  • $i$ бүрийн хувьд $a_{i}$ нь бүхэл тоо байна;
  • $i$ бүрийн хувьд $|a_{i}| ≤ k$ байна;
  • $a_{n} ≠ 0$.

Лимак саяхан $a_{0}, a_{1}, a_{2}, ..., a_{n}$ коэффициентүүдтэй $P$ хүчин төгөлдөр олон гишүүнттэй болжээ. Тэрээр $P(2) ≠ 0$ болохыг анзаарсан ба үүнийг өөрчлөхийг хүсжээ. Тэрээр $Q(2) = 0$ байх бөгөөд ахмад зэрэг нь $n$ байх хүчин төгөлдөр $Q$ олон гишүүнтийг гаргаж авахын тулд анхны олон гишүүнтийн 1 коэффициентын солих юм. Ингэж хийх аргын тоог тоолно уу. Хэрэв зорилгын олон гишүүнтүүдийн коэффициентууд нь ялгаатай бол уг 2 аргыг ялгаатай гэж тооцно.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10^{9}$) өгөгдөнө -- эдгээр нь олон гишүүнтийн ахмад зэрэг болон коэффициентуудын абсолют утгуудын хязгаарыг илэрхийлнэ.

2-дахь мөрөнд $n + 1$ ширхэг бүхэл тоо $a_{0}, a_{1}, ..., a_{n}$ ($|a_{i}| ≤ k, a_{n} ≠ 0$)-ууд өгөгдөнө -- эдгээр нь хүчин төгөлдөр олон гишүүнт -г дүрсэлнэ. Мөн $P(2) ≠ 0$ байна.

Гаралт

Нэг коэффициентыг сольсноор $Q(2) = 0$ байх хүчин төгөлдөр $Q$ олон гишүүнтийг гаргаж авах аргын тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 1000000000
10 -9 -3 5
Гаралт
3
Оролт
3 12
10 -9 -3 5
Гаралт
2
Оролт
2 20
14 -7 19
Гаралт
0

Тэмдэглэл

Эхний жишээнд, Бидэнд $P(x) = 10 - 9x - 3x^{2} + 5x^{3}$ олон гишүүнт өгөгдөнө.

Лимак нэг коэффициентыг 3-н янзаар сольж чадна:

  1. Тэрээр $a_{0} =  - 10$ болгоно. Дараа нь тэрээр $Q(x) =  - 10 - 9x - 3x^{2} + 5x^{3}$-тай болох ба $Q(2) =  - 10 - 18 - 12 + 40 = 0$ байна.
  2. Эсвэл тэрээр $a_{2} =  - 8$ болгоно. Дараа нь тэрээр $Q(x) = 10 - 9x - 8x^{2} + 5x^{3}$-тай болох ба $Q(2) = 10 - 18 - 32 + 40 = 0$ байна.
  3. Эсвэл тэрээр $a_{1} =  - 19$ болгоно. Дараа нь тэрээр $Q(x) = 10 - 19x - 3x^{2} + 5x^{3}$-тай болох ба $Q(2) = 10 - 38 - 12 + 40 = 0$ байна.

2-дахь жишээнд, бидэнд ижил олон гишүүнт өгөгдөнө. Харин $k$ нь $10^{9}$-ын оронд $12$-тай тэнцүү байх юм. Дээр тэмдэглэгдсэн эхний 2 арга нь хүчин төгөлдөр хэвээр байх боловч 3-дахь аргын хувьд тэрээр $|a_{1}| > k$ байх ба энэ нь зөвшөөрөгдөхгүй юм. Иймд, энэ удаад хариулт нь $2$ байна.

Сэтгэгдлүүдийг ачааллаж байна...