加了些数论知识 先看下剩余类的概念
一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类。
对于a%k=x b%k=y 若x!=y a与b有边相连 则a的剩余类 与b的剩余类l里的元素也是可以相连的 即 a ->b->a+k->b+k->a 所以有环
若x==y 则同一剩余类里元素都可以相连 a->a+k->a+2k->a 成环 且不会大于3*k
然后利用并查集就可以了 用vector存下可以与其满足对k取余为0的剩余类 枚举t t+k t+2*k时的情况 是不是形成 了环
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 300010
#define LL long long
vector<LL>q[N];
LL f[N];
LL find(LL x)
{
if(x!=f[x])
f[x] = find(f[x]);
return f[x];
}
int main()
{
LL i,j,k;
int flag = ,g;
scanf("%lld",&k);
for(i = ; i <= k*; i++)
f[i] = i;
for(i = ; i < k ; i++)
{
LL tt = (i*i)%k;
q[i].push_back((k-tt)%k);
q[(k-tt)%k].push_back(i);
}
for(i = ; i < k ; i++)
sort(q[i].begin(),q[i].end());
for(i = ; i <= k* ; i++)
{
int io = i%k;
int tt = unique(q[io].begin(), q[io].end()) - q[io].begin();
int t;
for(j = ; j < tt ; j++)
{
t = q[io][j];
if(t<i&&t>)
{
int tx = find(i);
int ty = find(t); if(tx==ty)
{
flag = ;
break;
}
else
f[tx] = ty;
}
if(t+k<i)
{
int tx = find(i);
int ty = find(t+k);
if(tx==ty)
{
flag = ;
break;
}
else
f[tx] = ty;
}
if(t+*k<i)
{
int tx = find(i);
int ty = find(t+*k);
if(tx==ty)
{
flag = ;
break;
}
else
f[tx] = ty;
}
}
if(flag)
{
g = i;
break;
}
}
if(flag)
printf("%d\n",g);
else
printf("-1\n");
return ;
}