D

给定n个Rc_i$,以及k,我们可以知道任意$x \mod c_i$ 的值,判断我们是否可以确定$x \mod k$

中国剩余定理

由中国剩余定理,若已知$x \mod a$和$x \mod b$,则可知$x \mod lcm(a,b)$
所以我们只需判断$k$ 是否为 $lcm(c_i)$ 的因子

由于$lcm(c_i)$较大,我们可以分解质因数来算
或者我们在求lcm的同时求之与k的gcd,最后判断这个数是否为k即可
(lcm就是每个质因子指数不断取最大值的过程,最后只要保证每个质因子指数都大于k的即成立

复杂度 $O(nlogn)$

E

有n枚硬币,面值为$c_i$,求这些硬币的子集组合成k后的子集还能组成的面值

DP

$d_{i,j,k}$ 表示前i枚硬币,是否可以组成j,子集是否可以组成k

$d_{i,j,k} = d_{i-1,j,k} \;or\; d_{i-1,j-c_i,k} \;or\; d_{i-1,j-c_i,k-c_i}$

复杂度 $O(nk^2)$