前言
upd(2021.02.13)：更改了所有已知错误与笔误；对一些评论有异议的地方增添了补充说明；更改了部分用词并修正了一些内容；修正了部分错误的 LaTeX。
另外，codecode 早已退役转战数竞，这次更新可能是对本博客的最后一次更新，但仍欢迎您反馈发现的问题/不懂的表述等说不定还会回来呢。
upd(2020.04.06)：更新了部分用词；修正了部分 LaTeX 错误；添加了部分内容。
楼下的大佬已经给出了正解，这里只是整理一下并帮他们补充完整证明。
作为数竞生，对于这种问题就想要给出一个完整的证明。（其实作为 OIer，只需要知道结论就可以了，不一定需要知道证明。（雾））
证明比较复杂，可能需要阅读并理解较长时间；如果不想看证明，可以跳到最后看结论。
证明过程
前置：费马定理，欧拉定理，拉格朗日定理。
这里只给出拉格朗日定理的证明。
前置 拉格朗日定理：设 p 为素数，对于模 p 意义下的整系数多项式
f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0\;(p\nmid a_n)
的同余方程 f(x)\equiv 0\pmod p 在模 p 意义下至多有 n 个不同解。
证明：对 n 使用归纳法。当 n=0 时，由于 p\nmid a_0，故 f(x)\equiv 0\pmod p 无解，定理对 n=0 的多项式 f(x) 都成立。
若命题对于 \deg f<n 的 f 都成立，由反证法，假设存在一个满足题目条件的 f 在模 p 意义下有着至少 n+1 个不同的解 x_0,x_1,\cdots,x_{n}。
可设 f(x)-f(x_0)=(x-x_0)g(x)，则 g(x) 在模 p 意义下是一个至多 n-1 次的多项式。现在由 x_0,x_1,\cdots,x_n 都是 f(x)\equiv 0\pmod p 的解，知对 1\leq i\leq n，都有
(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p
而 x_i \not\equiv x_0 \pmod p，故 g(x_i)\equiv 0\pmod p，从而 g(x)\equiv 0\pmod p 有至少 n 个根，与归纳假设矛盾。
所以，命题对 n 次多项式也成立，定理获证。
_补充：关于拉格朗日定理的证明中，由于 f(x_i)=0，故 f(x)-f(x_i) 就是 f(x)，不影响阅读。_
下面来看看阶与原根。
阶：由欧拉定理可知，对 a\in \mathbf{Z},m\in\mathbf{N}^{*}，若 \gcd(a,m)=1，则
a^{\varphi(m)}\equiv 1\pmod m
因此满足同余式 a^n \equiv 1 \pmod m 的最小正整数 n 存在，这个 n 称作 a 模 m 的阶，记作 \delta_m(a)。
原根：设 m \in \mathbf{N}^{*}，a\in \mathbf{Z}。若 \gcd(a,m)=1，且 \delta_m(a)=\varphi(m)，则称 a 为模 m 的原根。
关于阶有一个较为显然的性质：
若 a^n \equiv 1 \pmod m，则 \delta_m(a)|n。
证明： 对 n 除以 \delta_m(a) 作带余除法，设
n=\delta_m(a)q+r,0\leq r<\delta_m(a)
若 r>0，则
a^r\equiv a^r(a^{\delta_m(a)})^q\equiv a^n \equiv 1 \pmod m
这与 \delta_m(a) 的最小性矛盾。故 r=0，即 \delta_m(a)|n。
应评论：这里区分出 r>0 是为证明 r=0。
阶还有两个重要的性质。
性质 1：设 m\in\mathbf{N}^{*}，a,b\in\mathbf{Z}，\gcd(a,m)=\gcd(b,m)=1，则
\delta_m(ab)=\delta_m(a)\delta_m(b)
的充分必要条件是 \gcd(\delta_m(a),\delta_m(b))=1。
证明： 必要性。由 a^{\delta_m(a)}\equiv 1 \pmod m 及 b^{\delta_m(b)} \equiv 1 \pmod m，可知
(ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1 \pmod m
由前面所述阶的性质，有
\delta_m(ab)|\operatorname{lcm}(\delta_m(a),\delta_m(b))
又由于 \delta_m(ab)=\delta_m(a)\delta_m(b)，故
\delta_m(a)\delta_m(b)|\operatorname{lcm}(\delta_m(a),\delta_m(b))
即 \gcd(\delta_m(a),\delta_m(b))=1。
充分性。由 (ab)^{\delta_m(ab)}\equiv 1 \pmod m 可知
1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)} \pmod m
故 \delta_m(a)|\delta_m(ab)\delta_m(b)。结合 \gcd(\delta_m(a),\delta_m(b))=1 即得
\delta_m(a)|\delta_m(ab)
对称地，同理可得
\delta_m(b)|\delta_m(ab)
所以
\delta_m(a)\delta_m(b)|\delta_m(ab)
另一方面，有
(ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m
故
\delta_m(ab)|\delta_m(a)\delta_m(b)
综合以上两点即得
\delta_m(ab)=\delta_m(a)\delta_m(b)
性质 1 证毕。
性质 2：设 k \in \mathbf{N}，m\in \mathbf{N}^{*}，a\in\mathbf{Z}，\gcd(a,m)=1，则
\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
证明：注意到
a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m
\Rightarrow \delta_m(a)|k\delta_m(a^k)
\Rightarrow \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}|\delta_m(a^k)
另一方面，由 a^{\delta_m(a)}\equiv 1 \pmod m，可知
(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv 1 \pmod m
故
\delta_m(a^k)|\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
综合以上两点，得
\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
性质 2 证毕。
回到正题，我们下面来证明，关于怎样的 m，其原根存在。
首先，m=1,2,4 时，原根存在。
定理 1：对于奇素数 p，p 有原根。
证明：先证一个引理：
引理：设 a 与 b 是与 p 互素的两个整数，则存在 c\in\mathbf{Z} 使得 \delta_p(c)=\operatorname{lcm}(\delta_p(a),\delta_p(b))。
_该引理原来的证明存在错误，现已更改证明，感谢 @ lgLinZhengYu 及 @ Peanut_Tang 指出。_
记 r=\delta_p(a),t=\delta_p(b)，设它们的“标准分解”（这里对指数只要求 \max(\alpha_j,\beta_j)>0）分别为
r=\prod_{j=1}^s p_j^{\alpha_j},\quad t=\prod_{j=1}^s p_j^{\beta_j}
令 l 为所有使得 \alpha_j\leq\beta_j 的 p_j^{\alpha_j} 的乘积，令 m 为所有使得 \alpha_j>\beta_j 的 p_j^{\alpha_j} 的乘积. 记 r=lx,t=my. 则这样定义的 x,y 满足 \gcd(x,y)=1 且 \operatorname{lcm}(r,t)=xy。
由性质 2，\delta_p(a^l)=x,\delta_p(b^m)=y，则由性质 1，\delta_p(a^lb^m)=xy=\operatorname{lcm}(\delta_p(a),\delta_p(b))，即取 c=a^lb^m 即可。
回到原命题，对 1 \sim (p-1) 依次两两使用引理，可知存在 g\in \mathbf{Z} 使得
\delta_p(g)=\operatorname{lcm}\left(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\right)
这表明 \delta_p(j)|\delta_p(g)\;,j=1,2,\cdots,p-1，所以 j=1,2,\cdots,p-1 都是同余方程
x^{\delta_p(g)}\equiv 1\pmod p
的根。由拉格朗日定理，可知方程的次数 \delta_p(g) \geq p-1。
又由费马小定理，易知 \delta_p(g) \leq p-1，故 \delta_p(g)=p-1=\varphi(p)。
综上可知 g 为模 p 的原根。
定理 1 证毕。
定理 2：对于奇素数 p，\alpha \in \mathbf{N}^{*}，p^\alpha 有原根。
证明：一个基本的想法是将模 p 的原根平移。
先证明一个引理：
引理：存在模 p 的原根 g，使得 g^{p-1}\not\equiv 1 \pmod {p^2}
引理的证明：事实上，任取模 p 的原根 g，若 g 不满足条件，我们认定 g+p 满足条件。
易知 g+p 也是模 p 的原根。
我们有
\begin{aligned}(g+p)^{p-1}&\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\\&\equiv g^{p-1}+p(p-1)g^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv 1 \pmod {p^2}\end{aligned}
回到原题，我们证明若 g 是一个满足引理条件的原根，则对任意 \alpha\in\mathbf{N}^{*}，g 是模 p^{\alpha} 的原根。
首先，证明下面的结论：对任意 \beta\in\mathbf{N}^{*}，都可设
g^{\varphi(p^\beta)}=1+p^{\beta}\times k_{\beta}
这里 p\nmid k_{\beta}。事实上，\beta=1 时，由 g 的选取可知结论成立。现设上式对 \beta 时成立，则
\begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^{\beta})})^{p}\\&=(1+p^{\beta}\times k_{\beta})^p\\&\equiv 1+p^{\beta+1}\times k_{\beta} \pmod {p^{\beta+2}}\end{aligned}
结合 p\nmid k_{\beta} 可知命题对 \beta+1 成立。
所以命题对任意 \beta\in\mathbf{N}^{*} 都成立。
其次，记 \delta=\delta_{p^\alpha}(g)，则由欧拉定理，可知 \delta|p^{\alpha-1}(p-1)。
而由 g 为模 p 的原根，及 g^{\delta}\equiv 1\pmod {p^\alpha} 可知 (p-1)|\delta。
所以可设 \delta=p^{\beta-1}(p-1)，这里 1\leq \beta\leq \alpha。
现在利用之前的结论，可知
g^{\varphi(p^{\beta})}\not\equiv 1\pmod {p^{\beta+1}}\Rightarrow g^{\delta}\not\equiv 1\pmod {p^{\beta+1}}
结合 g^{\delta}\equiv 1\pmod {p^\alpha} 可知 \beta \geq \alpha。
综上可知，\beta=\alpha，即
\delta_{p^{\alpha}}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha)
从而，g 是模 p 的原根。
定理 2 证毕。
定理 3：对于奇素数 p，\alpha\in\mathbf{N}^{*}，2p^{\alpha} 的原根存在。
证明：设 g 是模 p^{\alpha} 的原根，则 g+p^{\alpha} 也是模 p^{\alpha} 的原根。
在 g 和 g+p^{\alpha} 中有一个是奇数，设这个奇数是 G，则 \gcd(G,2p^{\alpha})=1。
由欧拉定理，\delta_{2p^{\alpha}}(G)|\varphi(2p^{\alpha})。
而 G^{\delta_{2p^{\alpha}}(G)}\equiv 1\pmod {2p^{\alpha}}，故
G^{\delta_{2p^{\alpha}}(G)}\equiv 1 \pmod {p^{\alpha}}
利用 G 为模 p^{\alpha} 的原根可知 \varphi(p^{\alpha})|\delta_{2p^{\alpha}}(G)。
结合 \varphi(p^{\alpha})=\varphi(2p^{\alpha}) 可知 G 为模 2p^{\alpha} 的原根。
定理 3 证毕。
定理 4：对于 m\notin\{1,2,4\}，且不存在奇素数 p 及 \alpha \in \mathbf{N}^{*} 使得 m\in\{p^{\alpha},2p^{\alpha}\}，则对任意 a\in\mathbf{Z}，\gcd(a,m)=1，都有 \delta_m(a)<\varphi(m)，即模 m 的原根不存在。
证明：对于 m=2^{\alpha}，\alpha\in\mathbf{N}^{*},\alpha\geq 3，则对任意奇数 a=2k+1 均有
\begin{aligned}a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\&\equiv 1+C_{2^{\alpha-2}}^1(2k)+C_{2^{\alpha-2}}^{2}(2k)^{2}\\&\equiv1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2\\&\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k)\\&\equiv 1 \pmod {2^{\alpha}}\end{aligned}
其中最后一步用到 k 与 (2^{\alpha-2}-1)k 同奇偶，故其和为偶数。
若 m 不是 2 的幂，且 m 为符合题目条件的数，则可设 m=rt，这里 2<r<t 且 \gcd(r,t)=1。
此时，若 \gcd(a,m)=1，由欧拉定理可知
a^{\varphi(r)}\equiv 1 \pmod r\;,\quad a^{\varphi(t)}\equiv1\pmod t
注意到 n>2 时，\varphi(n) 为偶数，所以
a^{\frac{1}{2}\varphi(r)\varphi(t)}\equiv 1\pmod {rt}
进而
\delta_m(a)\leq\dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m)
定理 4 得证。
结论
上面的定理 1 到 4 完整的给出了原根的充要条件。截至目前，我们证明了仅有 1,2,4 或奇素数 p^{\alpha} 及 2p^{\alpha} 有原根，其它的数都没有原根。
那么我们可以先预处理素数及其幂次，及其幂次的 2 倍，\Theta(1) 的判断一个数有没有原根。
如果一个数有原根，可以先求出最小正原根。
王元于 1959 年证明了若 m 有原根，其最小原根是不多于 m^{0.25} 级别的。
事实上，由大量试验数据可以发现，对于足够大的 m，其最小正原根的大小不是多项式级别的。
——百度百科
可以感性理解一下，模 m 的原根有 \varphi(\varphi(m)) 个，密度很大，所以最小原根很小。
根据这个结论，我们可以从小到大枚举。由原根的定义，若 g 为模 m 的原根，则对于 \varphi(m) 的任意素因数 p，必有
g^{\varphi(m)/p}\not\equiv 1 \pmod m
同时，满足如上条件的 g，必将是原根。
我们可以预处理出 \varphi(m) 的所有素因数，快速幂来判断。
假如找到了一个原根 g，不难证明对于所有 \gcd(x,\varphi(m))=1 的 x，g^x 均为原根，所以模 m 的原根有 \varphi(\varphi(m)) 个。
所以我们可以在找到 g 后再枚举找出所有 m 的原根，排序后按要求输出。
复杂度不会算
注意需要开 longlong。