[日常训练]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
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