Given three positive integers $a$,$r$ and $n$, I need to calculate $\left\lfloor(a+\sqrt{r})^n\right\rfloor$ mod $p$, where $p$ is a prime.
Let $\left\lfloor(a+\sqrt{r})^n\right\rfloor=c+d\sqrt{r}$.
We can use binary exponentiation method to calculate $c$ mod $p$ and $d$ mod $p$. That doesn't help to calculate its floor modulo prime. Is there a fast method to do this without actually evaluate the whole thing? Any help will be appreciated.