What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity?

Given $M$ and $N$, is there a good way to find a prime $R$ such that $M$ is cubic non-residue modulo $R$ and $N$ is cubic residue modulo $R$?

Update after David Speyer's answer: Does the probability estimate hold good if $R$ is restricted to be between $M$ and $N$ and $M < 2N$ or $N < 2M$?