HCI '16 - Totient - Olympiads Online Judge

HCI '16 - Totient

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 0.2s

Memory limit: 16M

Authors:

zj97, damian, fanpu

Problem type

Functions $f(x)$ $f (x)$ and $g(y)$ $g (y)$ are defined below.

$\displaystyle f(x) = \begin{cases} 1, & \text{if } x = a^b \\ 0, & \text{if } x \ne a^b \end{cases}$ $f (x) = {\begin{cases} 1, & if x = a^{b} \\ 0, & if x \neq a^{b} \end{cases}$ where $a$ $a$ and $b$ $b$ are integers such that $a \ge 1$ $a \geq 1$ and $b > 1$ $b > 1$ .

$\displaystyle g(y) = \sum_{i=0}^y f(\phi(i)) \cdot \phi(i)$ $g (y) = \sum_{i = 0}^{y} f (ϕ (i)) \cdot ϕ (i)$ where $\phi(z)$ $ϕ (z)$ is Euler's totient function.

Given an integer $N$ $N$ , output $g(N) \pmod{10^9 + 7}$ $g (N) (\mod 10^{9} + 7)$ .

Input

A positive integer $N \le 1\,000\,000$ $N \leq 1 000 000$ .

Output

The value of $g(N) \pmod{10^9 + 7}$ $g (N) (\mod 10^{9} + 7)$ .

Constraints

Average scoring is used for this problem.

The first test case is the sample test below.

Afterwards, there will be 50 test cases worth 2 points each.

In all test cases, $1 \le N \le 1\,000\,000$ $1 \leq N \leq 1 000 000$ .

Sample Input

Copy

Sample Output

Copy

Explanation

$g(5) = 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 2 + 0 \cdot 2 + 1 \cdot 4 = 6$ $g (5) = 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 2 + 0 \cdot 2 + 1 \cdot 4 = 6$

Comments

0

r3mark commented on Dec. 17, 2016, 2:16 a.m.

What is f(x) if it satisfies both?

3

fanpu commented on Dec. 17, 2016, 2:22 a.m.

f(x) will be 1