来记录一下实现方式，真的有点妙。
首先通过打表可以发现进入循环节前的长度最多为 \(4\)，最小循环节的长度只有 \(1,2,3,6\)。
所以我们可以记录当前平方了几次，到达 \(4\) 次后算出长度为 \(6\) 的循环节中的数，之后只要记录平方次数模 \(6\) 后的值即可。
放一下 \(O(mod)\) 的打表代码。
#include<bits/stdc++.h>
using namespace std;
#define N 2018
#define Mod 2018
#define For(i,x,y)for(i=x;i<=(y);i++)
int dis[N];
bool type[N];
vector<int>vec;
int main()
{
int i,j,k,l;
For(i,1,Mod-1)
if(!dis[i])
{
vec.clear();
dis[j]=1;
j=i;
vec.push_back(j);
while(!dis[j*j%Mod])
{
dis[j*j%Mod]=dis[j]+1;
j=j*j%Mod;
vec.push_back(j);
}
For(k,0,vec.size()-1)
if(vec[k]==j*j%Mod)break;
For(l,k,vec.size()-1)dis[vec[l]]=vec.size()-k,type[vec[l]]=1;
if(k==vec.size()&&!type[j*j%Mod])dis[vec[--k]]=dis[j*j%Mod]+1;
else if(k)dis[vec[--k]]=1;
while(k--)dis[vec[k]]=dis[vec[k+1]]+1;
}
For(i,1,Mod-1)
if(type[i])cout<<dis[i]<<' ';
cout<<endl;
For(i,1,Mod-1)
if(!type[i])cout<<dis[i]<<' ';
return 0;
}