[日常训练]mod


Description

给定\(p_1,p_2,…,p_n,b_1,b_2,...,b_m\),
求满足\(x\;mod\;p_1\;\equiv\;a_1,x\;mod\;p_2\;\equiv\;a_2,...,x\;mod\;p_n\;\equiv\;a_n\)\(x\)\(b_1,b_2,...,b_m\)取模的结果.

Input

第一行两个整数\(n,m\).
接下来\(n\)行,每行有一个整数\(a_i\).
接下来\(m\)行,每行有一个整数\(b_i\).

Output

\(m\)行,每行一个整数,表示\(x\;mod\;b_i\)的结果.

Sample Input

4 3
1
2
3
2
11
23
100

Sample Output

1
0
23

HINT

\(m=100,0为随机生成的,\(p_i\)为第\(i\)小的质数.

Solution

中国剩余定理+高精度???
这题只需记录\(mod\;b_i\)结果.
\(ans.b[i]\)表示\(mod\;b_i\)的结果,\(mul.p[i]\)表示目前\(p_i\)寻找答案中每次加上的数,\(ans.p[i],mul.b[i]\)同理.
对于\(i\;\in\;[1,n]\),每次暴力\(+mul.p[i]\)直到\(ans.p[i]=a_i\),然后将每个\(mul.p[\;]\;\;\times\;p[i]\)(保证后面无论怎么操作,\(ans.p[i]\;\equiv\;a_i(mod\;p_i)\).
(\(ans.b[\;],mul.b[\;]\)同步进行以上\("+","\times"\)操作.)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 305
#define M 2000
using namespace std;
typedef long long ll;
struct mod{
    int p[N];ll b[N];
}ans,mul;
ll b[N]; 
int a[N],p[N],n,m,cnt;
bool u[M],flag;
inline void prime(){
    for(int i=2;cnt