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<b_i<10^9,b_i$为随机生成的,$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<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#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<n;++i){
if(!u[i]) p[++cnt]=i;
for(int j=1;j<=cnt&&p[j]*i<M;++j){
u[p[j]*i]=true;
if(!(i%p[j])) break;
}
}
}
inline void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]) flag=true;
}
for(int i=1;i<=m;++i)
scanf("%lld",&b[i]);
prime();
if(!flag){
for(int i=1;i<=m;++i){
ans.b[i]=1LL%b[i];
for(int j=1;j<=n;++j)
ans.b[i]=ans.b[i]*(ll)(p[j])%b[i];
}
for(int i=1;i<=m;++i)
printf("%lld\n",ans.b[i]);
return;
}
for(int i=1;i<=n;++i)
mul.p[i]=1%p[i];
for(int i=1;i<=m;++i)
mul.b[i]=1LL%b[i];
for(int i=1;i<=n;++i){
while(ans.p[i]!=a[i]){
for(int j=1;j<=n;++j)
ans.p[j]=(ans.p[j]+mul.p[j])%p[j];
for(int j=1;j<=m;++j)
ans.b[j]=(ans.b[j]+mul.b[j])%b[j];
}
for(int j=1;j<=n;++j)
mul.p[j]=mul.p[j]*p[i]%p[j];
for(int j=1;j<=m;++j)
mul.b[j]=mul.b[j]*(ll)(p[i])%b[j];
}
for(int i=1;i<=m;++i)
printf("%lld\n",ans.b[i]);
}
int main(){
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}