102 - Coprimes
مفهوم سوال :
این سوال به عنوان ورودی یه عدد طبیعی n < 10000 میده و از ما تعداد اعداد طبیعی کوچکتر یا مساوی n که نسبت به n اول هستن رو بدست بیاریم .
دو عدد رو نسبت به هم اول میگیم ، اگه ب.م.م اعداد 1 باشه .
حل:
با توجه به محدوده n ، چند روش برای حل داریم :
یک روش اینکه کاملا navie عمل کنیم ، یعنی هر بار n رو از ورودی بگیریم و برای همه اعداد کوچکتر یا مساوی n ، ب.م.م رو بدست بیاریم .
تابع بازگشتر اویلر برای بدست آوردن ب.م.م Log N زمان می بره ، و چون n تا عدد داریم order میشه : N log N
در روش دوم به جای شمردن اعدای که نسبت به n اول اند ، تعداد divisor های n رو بدست میاریم .
برای این کار :
یه آرایه می گیریم که از اول همه صفر هستن .
بعد شروع می کنیم به جلو رفتن رو آرایه ، در هر بار مقدار اندیس هایی که به محل فعلی بخشپذیرند رو یکی اضافه می کنیم .
جواب مساله میشه : N - array[N]
تو این سوال روش اول بهتره ، ولی در حالت کلی ، زمانیکه تعداد query ها بالا باشه ، بهتره از این روش تمام جواب ها رو از قبل بدست بیارید و با 1 order ازشون استفاده کنید.
