E. Нэгэн алдарт функцын итераци

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

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

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

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

Мэдээж та бүгд $n$-ээс бага, түүнтэй харилцан анхны эерэг бүхэл тоон утга болох $φ(n)$-ийг олж чадна. Гэвч бид $n$ тоо анхны тоон задаргаагаар өгөгдсөн үед $φ$ функц $k$ удаа давтагдсан $φ(φ(...φ(n)))$-ийн утгыг олох шаардлагатай болвол яах бэ?

$n$ ба $k$ өгөгдсөнөөр $φ(φ(...φ(n)))$-ийг тооцоол. Хариуг анхны тоон задаргаагаар хэвлэ.

Оролт

Эхний мөрөнд $n$-ийн ялгаатай анхны тоон хуваагчдын тоо болох $m$ ($1 ≤ m ≤ 10^{5}$) байна.

Дараагийн $m$ мөр бүрт $n$-ийн анхны тоон хуваагч болон түүний зэргийг илэрхийлэх $p_{i}, a_{i}$ ($2 ≤ p_{i} ≤ 10^{6}; 1 ≤ a_{i} ≤ 10^{17}$) гэсэн хос тоо байна. $a_{i}$-үүдийн нийлбэр $10^{17}$-аас хэтрэхгүй. Анхны тоон хуваагчид өсөх эрэмбээр өгөгдөнө.

Сүүлийн мөрөнд $k$ ($1 ≤ k ≤ 10^{18}$) өгөгдөнө.

Гаралт

Эхний мөрөнд $φ(φ(...φ(n)))$ тооны ялгаатай анхны тоон хуваагчдын тоог илэрхийлэх $w$-г хэвлэ.

Дараагийн $w$ мөр бүрт $φ(φ(...φ(n)))$-ийн анхны тоон хуваагч болон түүний зэргийг илэрхийлэх $q_{i}, b_{i}$ $(b_{i} ≥ 1)$ гэсэн хоёр бүхэл тоог зайгаар тусгаарлан хэвлэ. $q_{i}$ тоонууд өсөх эрэмбээр хэвлэгдэх ёстой.

Орчуулсан: Бат-Од

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

Оролт
1
7 1
1
Гаралт
2
2 1
3 1
Оролт
1
7 1
2
Гаралт
1
2 1
Оролт
1
2 100000000000000000
10000000000000000
Гаралт
1
2 90000000000000000

Тэмдэглэл

Бүхэл тооны анхны тоон задаргааны талаар эндээс уншиж болно: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.

$φ(n)$ функцын талаар эндээс уншиж болно: http://en.wikipedia.org/wiki/Euler's_totient_function.

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