Bài toán 3

Đề bài: Cho hàm F(x) được định nghĩa như sau: $ F(x) = \left\{\begin{matrix} x,  x \leq 9 \\ F(S(x)),  x > 9 \end{matrix}\right.$ với S(x) là tổng các chữ số của x. Tính: $F(n!),  1 \leq n \leq 500$ 
Ý tưởng: Ta có thể sử dụng bignum để tính n! và tính hàm F(x) một cách tuần tự. Tuy nhiên, nhận xét thấy nếu x chưa hết cho 9 thì S(x) cũng chia hết cho 9. Xét bài toán: 
Gọi $S^{n}(x) = \underbrace{S(x)\circ S(x).....\circ S(x)}_{n  S(x)} \Rightarrow  \left\{\begin{matrix} S^{0}(x) = x \\ S^{n}(x) = S^{n-1}(x) \circ S(x)\end{matrix}\right. $ 
Suy ra nếu $S^{0}(x) \vdots  9 \Rightarrow S^{i}(x) \vdots  9 \Rightarrow \exists i,  S^{i}(x) = 9,  (i) $ 
Vậy từ 1 số chia hết cho 9, sau 1 số phép biến S sẽ cho ra 9. 
Thuật toán:
Với $n < 6$: 
$ n = 1 \Rightarrow n! = 1 \Rightarrow F(x) = F(1) = 1$
$ n = 2 \Rightarrow n! = 2 \Rightarrow F(x) = F(2) = 2$ 
$ n = 3 \Rightarrow n! = 6 \Rightarrow F(x) = F(6) = 6$ 
$ n = 4 \Rightarrow n! = 24 \Rightarrow F(x) = F(24) = F(6) = 6$ 
$ n = 5 \Rightarrow n! = 120 \Rightarrow F(x) = F(120) = F(3) = 3$ 
Với $n \geq 6$: 
$n \geq 6 \Rightarrow n!  \vdots  9 \Rightarrow F(n!) = F(9)= 9$ (Áp dụng (i))
Mã nguồn:

#include <iostream>
using namespace std;

int main() {
int n, ans;
cin >> n;
switch (n) {
case 1: case 2: ans = n; break;
case 3: case 4: ans = 6; break;
case 5: ans = 3; break;
default: ans = 9;
};
cout << ans;
system("Pause");
return 0;
}