راه حلو کدوار میگم دیگه اثبات تیکه تیکش با خودتون... ایشالا قانع کننده باشه!
تعریف میکنیم:
$f(a, n)$ ینی تعداد اعداد کوچیکتر-مساوی $a$ که نسبت به $n$ اولن.
برا پیدا کردن $f(a, n)$ میایم بازگشتی میزنیم. چند حالت داره:
۱) اگه $a=1$ اونموقه $f(a, n) = 1$
۲) اگه $n = 1$ اونموقه $f(a, n) = a$
۳) اگه هیچکدوم از بالاییا نبود، میایم $n$‌ رو مینویسیم: $n = p^kq$ بصورتی که $p$ اوله و $gcd(p, q) = 1$ و $1 \le k$. حالا میشه فهمید که:
$$f(a, n) = f(a, q) - f(\lfloor\frac ap\rfloor, q)$$
حالا جواب مسئله هم میشه مجموع $f(a-1, x)$ برای $a < x < b $. $^_^$

پی نوشت: اینم کد تابع f که خودشو تست میکنه! D:
پی نوشت۲: زمان اجرای یبار صدا زدن تابع $f(a, b)$ رو میشه اینجوری بررسی کرد: حداکثر تعداد عملیات هایی که صدا زده شدن $f(a, n)$ به ازای همه ی $a$ های دنیا انجام میده رو میگیم $T(n)$. کلن برا $T(n)$ داریم که $T(n) \le 2T(q)$ که $q$ رو بالا تعریف کردیم. با استقرا میشه ثابت کرد که $T(n)$ حداکثر برابر دو به توان تعداد عوامل اول متفاوت $n$ـه که اون هم برای $n \le 50000$، حداکثر میشه $2^6 = 64$.
پس کلن زمان اجرای برنامه حداکثر $64\times b$ ـه که زیر ۱ ثانیه تموم میشه!
پی نوشت ۳:این همون $T(n)$ رو حساب کرده و به همونی که ما رسیدیم رسیده! ولی تو قسمت formulaـش نوشته که $\sum_{n=1}^bT(n) = O(blogb)$
پی نوشت ۴:اینم اثبات پی نوشت ۳!

یکم یاد این سوال افتادم : فلسفه ی وجود و یا عدم وجود جفت اعداد مسخره
حالا که نزدیک مرحله ۳ هم هست وقت بذارین حل کنینش!

میتونی از تابع فی اویلر استفاده کنی.برای همه اعداد a+1 تا b مجموع فی هاشون رو حساب کن. واضحه هر زوجی یبار شمرده شده دیگه.(وقتی مولفه بزرگشو میشمردیم).تابع فی از $O(NlgN)$ پیدا میشه.بقیه کارم که با $O(N)$ انجام میشه. در کل $O(NlgN)$ میشه.

الان کد میزارم.... پ.ن : کد