题解

CF Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) F

题目意思可以转化成给定$n$个非负二元组$(b _ i, a _ i),b _ i\in[0,a _ i)$，判断是否有一个值$V$满足：

$$V \equiv b _ i (mod~ a _ i)$$
我们来看如果$n=2$的话，只需要满足：
$$b _ 1\equiv b _ 2(mod ~ \gcd(a _ 1, a _ 2) )$$
这个结论是可以扩展的，只要任意一对二元组都满足条件，那么整体就是满足条件的。
证明的话，考虑CRT要求$a _ i$互质，但是因为每一对二元组都满足条件，因此我们可以把$a _ i$经过变换变成两两互质的，你可以先固定$a _ 1$，然后令$a _ i(i > 1) = lcm(a _ 1, a _ i) / a _ 1$，同时变换$b _ i$，然后继续固定$a _ 2$。。。
因为题目中$a _ i\leq 40$，因此$n$个二元组中最多有$40$个本质不同的二元组，那么我们就可以很方便的$O(n\cdot \max(a _ i))$扫出答案。