Cần giúp đỡ bài tập về tổng bình phương các chữ số của 1 số

hieu_nguyen24 · October 23, 2019, 3:10pm

Em chưa hiểu bài toán này lắm ạ. Xin mọi người đưa cho em định hướng làm bài ạ

Với số nguyên dương n, ta tạo số mới bằng cách lấy tổng bình phương các chữ số của nó, từ số mới nhận được ta lặp lại công việc trên. Nếu trong quá trình đó, ta nhận được số mới là 1, thì số n ban đầu được gọi là số hữu hạn.

Ví dụ:

Với n = 19 ta có 19 ->82 -> 68 -> 100 – > 1; Như vậy 19 là số hữu hạn. Với n = 12, ta có: 12 -> 5 -> 25 -> 29 – 85 -> 89 -> 145 -> 42 -> 20-> 4 -> 16 ->37 ->58 -> 89 -> 145. Như vậy 12 không phải là số hữu hạn.

Yêu cầu: Cho số nguyên dương x, in ra số hữu hạn nhỏ nhất lớn hơn x.

Dữ liệu vào: từ file văn bản NUMBER.INP gồm nhiều dòng, mỗi dòng ghi một số nguyên dương x với 1 <= x <= 10^14 và số dòng không vượt quá 20.
Đầy đủ bài toán đây ạ

SITUVN.gcd · October 22, 2019, 3:38pm

Đề bài không cho ví dụ và giải thích à?

12345
=>
1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55
=>
5^2 + 5^2 = 50
=>
5^2 + 0^2 = 25
...

Ở đây đề bài không nhắc đến cho phép lặp lại bao nhiêu lần. Nếu số vô hạn thì lặp vô tận!?

Việc bạn làm là:

Tách từng chữ số của số đó.
Tính bình phương của từng chữ số và cộng vào tổng.
Sau khi đã cộng xong cho tổng thì lặp lại từ 1. Tách từng chữ số của tổng nhận được…
Lặp cho đến khi tổng bằng 1.

kisuluoibieng · October 23, 2019, 4:57pm

tổng bình phương của nhiều số mà cộng lại bằng 1 có nghĩ là trong các số đó, có đúng một số bằng 1 và các số còn lại bằng 0
vậy các “số hữu hạn” là 10^x à?

đề này sai
bạn mô tả lại sai
Update: trường hợp 3 là không có gì sai, đề chỉ đơn giản là vậy
Update: idea ở trên đã sai, có những case như 5555 cũng đúng, như vậy với x <= 10^14 thì có:

1 <= n1 <= 8114 = 1134
1 <= n2 <= 813 = 243 (khi n1 = 999)
1 <= n3 <= 163 (khi n2 = 199)
1 <= n4 <= 162

như vậy tạo đồ thị 1 chiều có 162 đỉnh biểu diễn bằng ma trận 162x162, a[x,y] = 1 (x có đường đi tới y) khi tổng bình phương các chữ số của x là y

Với số n nhập vào, lặp cho tới khi 1 <= n <= 162.
Nếu được n = 1 thì trả ra yes
Nếu không thì kiểm tra xem đỉnh n có liên thông tới đỉnh 1 của đồ thị kia hay không, đó chỉnh là câu tar lời

bài này coi như O(1)

noname00 · October 22, 2019, 4:01pm

Giả sử số đầu tiên có L chữ số -> kết quả tính tổng bình phương các chữ số lần đầu tiên không quá 9^2 * L = 81 * L. Số này bé hơn nhiều so với số đề bài cho, limit vẫn nằm trong khoảng int (dù cho số đầu tiên cho dài đến mấy cũng không thể cho quá to được - bộ nhớ máy tính cần tải được).

Do vậy có thể bruteforce check khả năng tất cả các số từ 1 -> 81*L, sau đó in ra chỉ với O(1).

hieu_nguyen24 · October 23, 2019, 1:06pm

Với số nguyên dương n, ta tạo số mới bằng cách lấy tổng bình phương các chữ số của nó, từ số mới nhận được ta lặp lại công việc trên. Nếu trong quá trình đó, ta nhận được số mới là 1, thì số n ban đầu được gọi là số hữu hạn. […]

(đã copy lên #1 - rogp10)

hieu_nguyen24 · October 23, 2019, 12:44pm

sao để tách chữ số để tính đc v anh ? Dùng mảng à

rogp10 · October 24, 2019, 1:12pm

Đã copy lên #1

Precomputation: Do tổng bình phương tối đa là 81*14 = 1134 nên ta tính sẵn một bảng để đó (tính thêm bảng từ 0 đến 9^2 nữa). Áp dụng thuật toán thỏ - rùa tìm chu kì nhanh chóng. Lấy được bảng tổng xong thì ghi thẳng vào code

Query: dùng pp sinh để tính nhanh rồi so với bảng đã tính ở trên. Sau khi rà sơ sơ thì số đúng dạng chiếm ~ 1/7 số tự nhiên.