?
【題目鏈接】?http://acm.timus.ru/problem.aspx?space=1&num=1682
?
【題目大意】
給出k，從1開始不斷地加一并把這個數寫在黑板上，如果寫上的數字和之前的數字滿足
(a+b*b)%k=0或者(b+a*a)%k=0就在他們之間連一條線，如果黑板上出現環就結束，問能寫幾個數
?
【題解】
我們發現寫到2k-1的時候，就一定會產生一個環，所以我們只要枚舉數字
往滿足要求的地方連邊，判斷是否出現環即可
?
【代碼】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N=300010;
int f[N],n,pre[N];
vector<int> G[N];
int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}
void solve(){for(int i=1;i<=3*n;i++)pre[i]=0,f[i]=i,G[i].clear();G[n-1].push_back(1);for(LL i=2;i<=3*n;i++){LL t=n-(i*i)%n;while(t<i){if(t){if(sf(t)==sf(i)){printf("%lld\n",i);return;}f[f[t]]=f[i]; pre[t]=i;}t+=n;}t=i%n;for(int j=0;j<G[t].size();j++){int p=G[t][j];if(pre[p]==i)continue;if(sf(p)==sf(i)){printf("%lld\n",i);return;}f[f[p]]=f[i];}G[n-(i*i)%n].push_back(i);}
}
int main(){while(~scanf("%d",&n))solve();return 0;
}
