CDRSANJ spoj

https://www.spoj.com/problems/CDRSANJ/

Đề bài: 

CODER SANJAY chuẩn bị đưa bài toán đầu tiên của mình lên SPOJ. Vì đây là bài toán đầu tiên, anh ấy muốn nó phải thật dễ để ai cũng có thể AC. Bài toán được cho như sau: 

Gọi $f(x)$ là một hàm số, sao cho: 

1. $f(x) = 0$ tại $x = 0$
2. $f(x) = 1$ tại $x = 1$
3. $f(x) = 2$ tại $x = 2$
4. $f(x) = 0$ với mọi $x$ là số lẻ khác $1$
5. $f(ab) = f(a) + f(b)$ với $a$ và $b$ là hai số nguyên sao cho $a + b$ nhỏ nhất.

Giới hạn: $0 < x < 10^5 + 1$

Input: 

một và chỉ một số nguyên $x$.

Output: 

Giá trị $f(x)$.

Example:

Input: 

$4$

Output:

$4$

Solution: 

Ở đây ta để ý mấy cái tô đỏ thôi, mấy cái khác không quan trọng.
Giả sử ta có $x = 4 $(theo input). Vì $f(ab) = f(a) + f(b)$ nên $f(4)$ có thể bằng $f(2\times 2)$ hoặc $f(1\times 4)$.  Nhưng vì đề bảo tìm $a$ và $b$ sao cho $f(a) + f(b)$ nhỏ nhất, nên $f(4) = f(2\times 2) = f(2) + f(2) = 2 + 2 = 4$, đúng như input.

Giả sử ta có $x = 12$
$f(12) = f(2 \times 6) = f(3 \times 4)$.
Ta để ý: 

• $f(2 \times  6) = f(2) + f(6) = f(2) + f(3 \times  2) = 2f(2) + f(3)$.
• $f(3 \times  4) = f(3) + f(4) = f(3) + 2f(2)$.

Và đáp án chúng ta thu được vẫn là $f(12) = 4$.

Vậy chúng ta có thể suy ra được solution: 

• Nếu $x \in \{0, 1, 2\}$ thì trả về $x$. 
• Nếu $x = 2k+1\ (k \in \mathbb{Z}, k \geq 1)$: trả về $0$.
• Nếu $x = 2k\ (k \in \mathbb{Z}, k \geq 1)$: trả về $\log_2(x)$.

Code:

Độ phức tạp: $\mathcal{O}(\log n)$