ارباب حلقه‌ها


  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

گالوم و فرودو در مسیر رفتن به موردور برای از بین‌بردن حلقه حوصله‌شان سررفته و می‌خواهند بازی کنند. این بازی به این‌صورت است که فرودو nn عدد طبیعی به گالوم می‌دهد و می‌گوید بین هر عدد و مقسوم‌علیه های آن و هرکدام از مقسوم‌علیه‌ها و مقسوم‌علیه‌هایشان و به همین‌ترتیب تا ۱، یک یال بدون‌جهت وجود دارد. دراین گراف هیچ راسی به خودش یال ندارد. حال گالوم باید تعداد دورهای موجود در گراف حاصل را بین کند. اگر گالوم درست بگوید؛ فرودو حلقه را برای مدتی به او می‌دهد. به گالوم کمک کنید تا بتواند حلقه را به‌دست آورد.

ورودی🔗

ورودی شامل دو خط می‌باشد که در خط اول عدد طبیعی nn و در خط دوم nn عدد طبیعی با فاصله از هم آمده‌اند. اعداد ورودی در خط دوم حداقل ۱ و حداکثر ۱۰۰۰ می‌باشند.

1n1 0001 \le n \le 1\ 000

خروجی🔗

خروجی تنها شامل یک خط است که تعداد دورهای موجود در گراف حاصل را نشان می‌دهد.

مثال🔗

ورودی نمونه ۱🔗

4
1 2 4 8
Plain text

خروجی نمونه ۱🔗

7
Plain text
توضیحات نمونه‌ی یک

توضیح تصویر در گراف حاصل ۷ دور وجود دارد.

ورودی نمونه ۲🔗

3
6 4 5 
Plain text

خروجی نمونه ۲🔗

6
Plain text
توضیحات نمونه‌ی دو

توضیح تصویر در گراف حاصل ۶ دور وجود دارد.