1 năm, 4 tháng trước

Độ bá đạo: http://vn.spoj.com/problems/VOSPOW/

Thuật toán của mình:

- kt = k^t mod phi(base)

- Sinh ra dãy A

- Duyệt hết dãy A: badao = (badao + ai^kt ) % base;

(Hàm mủ log(n))

Mà sao toàn 9 điểm hoài.

Mọi người ai 100 rồi xin chỉ thêm cách làm?

1 năm, 4 tháng trước

Bài này có một nhận xét là só lượng số nguyên tố không nguyên tố cùng nhau với BASE là cỡ log2(BASE) hay số lượng số nguyên tố x để [x, BASE] > 1 sẽ là cỡ log2(BASE). Dựa vào tính chất này, ta có thể dùng đình lý euler để tính x^Q nhanh trong đó x là số nguyên tố và [x, BASE] = 1. Các số nguyên tố x mà [x, BASE] > 1, thì sẽ tính tay x^Q. Khi tính được các số nguyên tố lũy thừa Q rồi thì tính các số tự nhiên khác lũy thừa Q cũng sẽ dựa vào đó mà tỉnh a một cách dễ dàng.

Tuy nhiên bài này là bài tương đối khó nếu bạn chưa làm đc bây giờ thì cứ để đó. Luyện sang những bài khác lúc khác quay lại làm cũng đc.