Phân tích số n thành tổng của các số có số mũ quy định


(Lan Trần) #1

Chào mọi người. Mình có câu hỏi muốn tham khảo các bạn.

Cho số n và số mũ m. Phân tích số n thành tổng của các số có số mũ quy định.

Ví dụ:

Cho n=10 và m=2.
Cho ta 3 trường hợp: 10^2; 1^2+… và 6^2+8^2.


(Ngô Anh Đức) #2

Giả sử n được phân tích thành k số a1 a2 … ak

Thỏa mãn a1^m+...+ak^m= n

a1 < a2 < ... < ak nên k.a1^m < n < k.ak^m

Đặt

i = [căn bậc m của n]
k0 = [căn bậc m của k]

=> k.a1^m < (i+1)^m 
i^m < k.ak^m

=> a1 < (i+1)/k0
ak > i/k0

Có giới hạn của a1 và ak rồi, bây giờ cho k chạy từ 1 đến i sẽ nhanh hơn


89% Thành viên có cách giải cho một câu hỏi. Bạn thì sao?