首页 > 代码库 > URAL 1682 Crazy Professor (并查集)
URAL 1682 Crazy Professor (并查集)
【题目链接】 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;}
URAL 1682 Crazy Professor (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。