پاسخ - SGU 499

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=499

 

ترجمه :

n نفر داریم که دو به دو با هم دوست اند ، هر کدام از افراد یک «عدد دوستی» دارد . میزان دوستی دو نفر را برابر با بزرگترین مقسوم علیه مشترک(ب.م.م) عدد دوستی آن دو نفر میدانیم .می خواهیم بدانیم بیشترین میزان دوستی بین این n نفر چقدر است .

 

ورودی :

در اولین خط ورودی عدد n داده می شود

و در n خط بعدی اعداد دوستی افراد داده می شود .

همه ی اعداد دوستی بین 1 و 1000000 هستند (شامل خود این اعداد)

 

خروجی :

در تنها خط خروجی بیشترین میزان دوستی بین این n نفر را چاپ کنید .

 

مثال : 

ورودی نمونه :

4
9
15
25
16

خروجی نمونه :

5

---

شرح راه حل :

 

از آنجایی که پاسخ فقط می تواند اعداد بین 1 تا 1000000 باشد ، به ازای هر عدد   چک می کنیم که زوجی از افراد وجود دارد که میزان دوستی آنها برابر با x باشد یا نه .

پاسخ نهایی بزگترین x است که اینکار برای آن ممکن باشد . اگر و تنها اگر یک رابطه دوستی با میزان دوستی x داریم که بیشتر از یکی از مضرب های x در بین عدد های دوستیمان داشته باشیم .

پس به ازای هر عدد  چک می کنیم که چند تا از مضرب های آن در بین عدد های دوستی وجود دارند ، اگر این تعداد بیشتر از 1 بود x پاسخ نهایی خواهد بود . 

 

الگوریتم ارائه شده از  است .(چرا؟)

 

کد : https://snipt.net/JahanaraCo/499-sgu/