المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۲۷:سوال ۲

عکس فی

هوشنگ به تازگی در دبیرستان با تابع فی-اویلر، یعنی $\phi$ آشنا شده است. $\phi(n)$ تعداد اعداد طبیعی کوچکتر مساوی $n$ است که نسبت به $n$ اول اند. مثلا $\phi(1) = 1$ و $\phi(9) = 6$ است.

همچنین او می‌داند که اگر $P(n)$ مجموعه همه‌ی عوامل اول $n$ باشد:

$$\phi(n) = n \prod \limits_{p \in P(n)} \frac{p-1}{p}$$

هوشنگ تابع $f$ را اینگونه تعریف می‌کند:

$$f(n) = \sum \limits_{i \in \mathbb{N}, \phi(i) = n} i^2$$
هوشنگ از شما خواسته به سوالات زیر پاسخ دهید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10067$ محاسبه شده‌اند.

$2$- الف ($11$ نمره) : باقی‌مانده‌ی تقسیم $f(60)$ بر $\Delta$ چند است؟

پاسخ

4871

$2$- ب ($11$ نمره) : باقی‌مانده‌ی تقسیم $f(2^{50})$ بر $\Delta$ چند است؟

پاسخ

6043

$2$- ج ($11$ نمره) : باقی‌مانده‌ی تقسیم $f(2350194604833600)$ بر $\Delta$ چند است؟

پاسخ

4867


ابزار صفحه