Ok, so how do use Fermat’s theorem? Like if an xi comes, what do you do? Take xi mod (p-1) or what?
@divakar_tomar: The assertion a^p\equiv a\pmod p~ is true for any integer a and prime p. The requirement \gcd(a,p)=1~ is only needed for the assertion a^{p-1}\equiv 1\pmod p~ because you divide both sides by a then. When \gcd(a,p)\neq 1~ that is, p divides a, then a^p is divisible by p as well so we can still apply the reduction stated by @junior94 here.
1 Like
So we take xi mod p or xi mod (p-1) to make reduction?
FFT part described in editorial is not required and also “not possible”.
It is hard to do that here but it is possible!