Let $n=1,$ we get: $a_1=1.$ For all $n \geq 2,$ $$(n^2+1)a_n=n(a_{n^2}+1) \rightarrow n \mid a_n \rightarrow a_n=nb_n, b_n \in N^*.$$$\rightarrow (n^2+1)nb_n=n(n^2b_{n^2}+1) \leftrightarrow (n^2+1)b_n=n^2b_{n^2}+1.$ $$\leftrightarrow (n^2+1)(b_n-1)=n^2(b_{n^2}-1), (1) \rightarrow n^2 \mid b_n -1.$$$\rightarrow b_n-1=n^2c_n \Rightarrow b_{n^2}-1=n^4c_{n^2},$ where $c_n \geq 0.$ Assert this in $(1),$ we get: $(n^2+1)n^2c_n=n^2n^4c_{n^2} \rightarrow c_{n^2} =\frac{n^2+1}{n^4}c_n \leq \frac{1}{n}c_n.$ $$\Rightarrow c_{n^{2^k}}\leq \frac{1}{n^{2^{k-1}}}.c_{n^{2^{k-1}}} \leq \frac{1}{n^{2^{k-1}}}.\frac{1}{n^{2^{k-2}}}.c_{n^{2^{k-2}}}\leq ...\leq \frac{1}{n^{2^{k-1}}}.\frac{1}{n^{2^{k-2}}}...\frac{1}{n}.c_n=\frac{1}{n^{2^k}-1}.c_n,$$which is converge to $0.$ So $\exists$ suffice large $t:$ $c_{n^{2^t}}=0.$ By backward induction, form $i=t$ to $i=t-1;...;i=0,$ we can prove that $c_{n^{2^i}}=0.$ Or $c_n=0.$ Thus, $$a_n=n, \forall n.$$ Q.E.D