Masala #0418
TreeFactors
Azimjon \(N\) sonidan ildizi \(N\) ga teng bo’lgan sikil mavjud bo’lmagan daraxt hosil qilishni ajoyib yo’lini o’ylab topdi, ya’ni u daraxni quyidagicha hosil qiladi.
- \(N\) sonining tub bo’luvchilari ichidan eng kichigini tanlab oladi ya’ni \(P_i\) ni;
- \(N/P_i\) va \(P_i\) sonlarini \(N\) ga ulaydi;
- \(N\) ning yangi qiymati uchun \(N=N/P_i\) ni oladi.
Bu jarayondi N soni tub son bo’lib qolguncha davom ettiradi. Sizning vazifangiz hosil bo’lgan daraxtning ildizidan tub qiymatli shoxlarining uchigacha bo’lgan masofalar yig’indisini hisoblash(ikki bog’langan tugunlarni o’rtasidagi masofa 1 ga teng deb hisoblang).
Misol: \(N=8\) bo’lgan holat rasimda tasvirlangan.
Kirish fayilida yagona natural son \(N(2 \le N \le 10^{12})\).
Сhiqish fayilida yagona son masalaning javobi.
# | input.txt | output.txt |
---|---|---|
1 |
3 |
0 |
2 |
8 |
5 |