C. Майк ба Шоколадны хулгайчид

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

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

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

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

Майк-ын амьдардаг тосгонд нэгэн муу мэдээ ирсэн бөгөөд тухайлбал хэсэг хулгайчид орон нутгийн үйлдвэрээс нэг хайрцаг шоколад хулгайлжээ! Үнэхээр аймшигтай!

Амттай зүйлд дурлахаас гадна уг нутгийн хулгайчид нь үнэхээр шунахай гэдгээрээ алдартай. Хэрэв нэг хулгайч хэсэг шоколадыг өөртөө зориулан хулгайлахад, дараагийн хулгайч нь өмнөх хулгайчаасаа яг $k$ дахин их шоколадыг хулгайлдаг байв. $k$ ($k > 1$)-ын утга нь зөвхөн хулгайч нарын мэддэг нууц бүхэл тоо ажээ. Мөн түүнчлэн хулгайч болгоны цүнх нь хамгийн ихдээ $n$ ширхэг шоколад багтааж болдог бөгөөд (хэрэв тэд илүү ихийг авахыг хүсвэл уг хулгай нь амжилтгүй болох юм) уг хулгайн хэрэгт яг 4-н хулгайч холбогдсон байв.

Харамсалтай нь зөвхөн хулгайч нар л $n$-ын утгыг мэдэх боловч хулгайч нарын шоколад хулгайлах аргын тоо нь $m$ (тогтмол $n$-ын хувьд боловч $k$ нь тогтмол биш байна) гэсэн цуурхал гарсан байв. Хэрэв хулгайч нарын нэг нь (хулгайч нар нь шоколад авсан дарааллаараа дугаарлагдсан байна) уг аргууд дээр өөр тооны шоколад авсан байвал 2 аргыг ялгаатай гэж үзнэ.

Майк хулгайч нарыг мөшгөхийг хүссэн бөгөөд иймд тэрээр тэдгээрийн цүнх ямар болохыг мөн $n$-ын утгыг мэдэхийг хүсжээ. Тэгвэл боломжит хамгийн бага $n$-ын утгыг олно уу эсвэл түүнд уг цуурхал нь худал бөгөөд ийм байх $n$ тоо байхгүй болохыг хэлж өгнө үү.

Оролт

Дан мөрөнд цуурхлын дагуу яригдаж буй хулгайч нарын шоколад хулгайлах аргын тоог илэрхийлэх бүхэл тоо $m$ $(1 ≤ m ≤ 10^{15})$ өгөгдөнө.

Гаралт

Хулгайч нарын цүнхэнд багтааж болох хамгийн их шоколадны хэмжээг илэрхийлэх ганц бүхэл тоо $n$-г хэвлэнэ үү. Хэрэв цуурхлын дагуу байх нэгээс олон $n$-ын утга байвал тэдгээрээс хамгийн бага утгыг нь хэвлэнэ үү.

Хэрэв уг цуурхал нь худал бөгөөд өгөгдсөн $m$-ын хувьд $n$ тоо оршин байхгүй байвал $ - 1$ гэж хэвлэнэ үү.

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

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

Оролт
1
Гаралт
8
Оролт
8
Гаралт
54
Оролт
10
Гаралт
-1

Тэмдэглэл

Эхний жишээнд яг нэг ширхэг хулгайлах аргатай байх хамгийн бага $n$-ын утга нь $n = 8$ байх бөгөөд хулгайлагдсан шоколадны хэмжээнүүд нь $(1, 2, 4, 8)$ (хулгайч бүрийн хулгайлсан шоколадны хэмжээг үзүүлэв) байх юм.

2-дахь жишээнд $8$ ширхэг хулгайлах аргатай байх хамгийн бага $n$-ын утга нь $n = 54$ байх бөгөөд энэ тохиолдолд хулгайлагдсан шоколадны хэмжээнүүд нь $(1, 2, 4, 8),  (1, 3, 9, 27),  (2, 4, 8, 16),  (2, 6, 18, 54),  (3, 6, 12, 24),  (4, 8, 16, 32),  (5, 10, 20, 40),  (6, 12, 24, 48)$ байж болох юм.

3-дахь жишээнд яг $10$ ширхэг хулгайлах аргатай байх ямар нэгэн $n$-ын утга оршин байхгүй байна.

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