题目链接：bzoj1407 题目大意： 有n个野人，野人各自住在第c[i]个山洞中（山洞成环状），每年向前走p[i]个山洞，到这个山洞住下来。 每个野人的寿命为l[i]，问至少需要多少个山洞，才能让野人在有生之年永远不住在同一个山洞。 题解： 拓展欧几里德 n≤15，所以直接从小到大枚举答案。 然后再枚举每对野人看看是否合法。 设野人 i i、jj相遇的时间为第k年 据题意

题目传送门 分析 可以看到，题目中涉及到很多合并和查询操作，所以我们可以用并查集来维护每列的信息。 不过这题需要而外维护两个数组 d i s i dis_i disi​ 和 s i z i siz_i sizi​，分别表示距离序列头部的距离和以 i i i 做头的序列长度。 合并时需要更新 s i z siz siz 和 d i s dis dis。 查询 i i i 和

Description 传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。 有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。 这M个

枚举m，n^2判断 对于野人i,j，(H[i]+x*S[i])%m==(H[j]+x*S[j])%m,且x<=O[i]&&x<=O[j],他们才有可能相遇 化简得:(S[i]-S[j])*x+y*m=C[j]-C[i],扩欧解x最小值，判断 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>