A further caveat to that is that the "36%" figure is a maximum figure, on the basis you are resident in China.
If you are on a commuting contract, or indeed with the new overseas based options available, then this figure drops substantially - closer to 10-15% tax paid.
Re a tax certificate; I understand at least China Southern do provide a tax paid certificate, but on the basis of 15-30% depending on days spent in China.