洛谷P2421 [NOI2002]荒岛野人

题意

题目链接

分析

一道比较水的题目,手摸一下样例,可以发现:假设当前有(m)个洞,那么对于每两个人((i)(j)),他们不会相遇当且仅当满足以下条件:

方程:

[C_i+x*P_i equiv C_j+x*P_j (mod m) ]

其中(x)有解且(x)大于(min{(L_i,L_j)})

那么我们直接枚举答案(m)(i,j)然后每次暴力(exgcd)判断和求解即可,如果当前的(m)不行就枚举下一个

看上去时间复杂度会爆炸,事实上不会...这题好坑...

原文地址:https://www.cnblogs.com/Akmaey/p/14098498.html