Codeforces Gym 101252D&&floyd判圈算法学习笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Gym 101252D&&floyd判圈算法学习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1312字，纯文字阅读大概需要2分钟。

内容图文

一句话题意：x₀=1，x_i+1=(Ax_i+x_i%B)%C，如果x序列中存在最早的两个相同的元素，输出第二次出现的位置，若在2e7内无解则输出-1。

题解：都不到100天就AFO了才来学这floyd判圈算法。

介绍一下floyd判圈算法：该算法适用于在线性时间复杂度内判断有限自动机、迭代函数、链表中是否有环，求环的起点（即链长）和环长。

可以先这么做：首先从起点S出发，给定两个指针，一个快指针一个慢指针，然后每次快指针走1步，慢指针走2步，直到相遇为止。如果已经到达终点/达到规定步数时仍然没有相遇，说明图中没有符合条件的环。如果相遇了，可以确定进入了环（如图则在M点相遇），接下来就要计算环长和环起点。

计算环长：令其中一个指针一直走下去，记录步数即可，因为其在环内，最终一定会在线性复杂度内再次返回节点M。

计算环起点：令其中一个指针位于M，另一个回到S，然后两者以相同速度推进，相遇的点就是环的起点。

证明：留坑，后序补上。

Codeforces Gym 101252D：显然是一道裸题，上code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7;
ll a,b,c,s,r,x,y; 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>a>>b>>c;
    x=y=1;
    while(s<N)
    {
        s++;
        y=(a*y+y%b)%c,y=(a*y+y%b)%c;
        x=(a*x+x%b)%c;
        if(x==y)break;
    }
    if(x!=y){puts("-1");return 0;}
    while(r<N)
    {
        r++;
        y=(a*y+y%b)%c;
        if(x==y)break;
    }
    if(x!=y){puts("-1");return 0;}
    s=0,y=1;
    while(x!=y&&s<N)
    {
        s++;
        y=(a*y+y%b)%c;
        x=(a*x+x%b)%c;
    }
    s+=r;
    if(x==y&&s<=N)cout<<s;
    else puts("-1");
    return 0;
}

View Code

 

内容总结

以上是互联网集市为您收集整理的Codeforces Gym 101252D&&floyd判圈算法学习笔记全部内容，希望文章能够帮你解决Codeforces Gym 101252D&&floyd判圈算法学习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---