Editorial for Bedao Regular Contest 08 - TRIPLET


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Khi ~K~ lẻ, một bộ ba ~(a, b, c)~ thỏa mãn khi tất cả đều chia hết cho ~K~ nên số cách chọn trong trường hợp này là ~(\frac{n}{k})^3~ (xuất hiện mũ ~3~ vì ta cần tính cả số cách chọn của bộ ba).

Khi ~K~ chẵn, một bộ ba ~(a, b, c)~ thỏa mãn khi tất cả đều chia hết cho ~K~, hoặc tất cả đều đồng dư ~\frac{K}{2}~ mod ~K~. Đếm các bộ ba như thế bằng cách đếm số các số bé hơn ~N~ mod ~K = 0~ hoặc ~\frac{k}{2}~. Vì vậy, số cách chọn trong trường hợp này là ~(\frac{n + \frac{k}{2}}{k})^3 + (\frac{n} {k}) ^ 3~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.