We can write the given condition as $(n^{1008})^2+(2016^{1008})^2$ and by a very famous lemma we know that the sum of 2 squares can never be divisible by $p=4k+3$.So (a) is infinite and (b) is infact an empty set.

I think there are also infinitely many primes $p=4k+1$ such that $p\nmid n^{2016}+2016^{2016}$ for all $n$. Suppose $p\mid n^{2016}+2016^{2016}$. As $2016= 2^5\cdot 3^2\cdot 7$, we have $(p,2016)=1$ so $p\mid u^{2016}+1$ where $u\equiv n\cdot 2016^{-1}\pmod{p}$. Further, let $d$ be the smallest positive integer for which $u^d\equiv 1\pmod{p}$. Then, $d\nmid 2016$ and $d\mid 2\cdot 2016$. This forces $v_2(d)=v_2(2016)+1=6$. We also have $d\mid p-1$ by Fermat, so $p\equiv 1\pmod{64}$ is a necessity. Now, just choose $p$ such that $p\equiv 1\pmod{4}$ and $p\not\equiv 1\pmod{64}$. For example, $p\equiv 5\pmod{64}$ is a valid choice and there're infinitely many such primes due to Dirichlet.