Đề 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;
}
No comments:
Post a Comment