\(\\\)
- \(n\le 15\)，保证答案小于 \(10^6\)。
\(\\\)
Solution
首先要注意到答案不具有单调性，手搓两组样例就能发现剩余系不同重合位置是不同的。
然后想到从小往大枚举答案然后验证。注意下界是 \(max\{C_i\}\)
验证选择最暴力的方法即可。
加入现在枚举共有 \(len\) 个洞。
考虑两个野人 \(i,j\) ，假如说 \(k\) 年后他们重合，那么 \(k\) 应该满足
\[ C_i+kP_i\equiv C_j+kP_j\pmod{len} \] 移项\[ k（P_i-P_j)\equiv C_j-C_i\pmod{len} \] 这不是同余方程么.....直接扩欧求一个最小的正整数解 \(k\) 即可。如果 \(k>min(L_i,L_j)\) 证明在相遇之前他们之中就有人死了，所以没有问题。
特殊的，如果无解代表他们这辈子也碰不到，也是合法的。
复杂度 \(O(ans\times 15^2\times log 10^6)\)
\(\\\)
Code
#include#include #include #include #include #include #include #define N 20#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,mx,c[N],p[N],l[N];void exgcd(int a,int b,int &x,int &y,int &g){ if(!b){g=a;x=1;y=0;} else{exgcd(b,a%b,y,x,g);y-=a/b*x;}}inline bool valid(int now){ R int a,b,d,x,y,g; for(R int i=1;i