HDU - 5238（剩余定理）

2019-04-14 17:37发布

站内文章 / 模拟电子
11465 0 1241
题意： 给出一个计算的序列，包含{+,*,^}三种运算。给出两种操作，1是给出初始值，求按照序列计算的答案，2是修改序列中某个位置的数和运算符。 描述： 问题最后要把结果对29393去模，把模拆分为7*13*17*19,那么如果能够在每次修改后求出 t1 = ans%7; t2=ans%13, t3=ans%17, t4=ans%19. 那么问题的解就是模方程组 『   x≡t1(mod)7;  x≡t2(mod)13;
  x≡t3(mod)17;
  x≡t4(mod)19;
 』   方程组的解。 #include #include #include #include #include using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define rep(i,n) for(int i=0;i>=1; a=(a*a)%dd; } return ans; } char src[10]; void read(int i){ scanf("%s",src); int len=strlen(src); str[i]=src[0]; num[i]=0; for(int j=1;j>1; build(lson,i); build(rson,i); push_up(l,r,rt,i); } void update(int l,int r,int rt,int i,int p){ if(l==r) { rep(j,m[i]) sum[rt][i][j]=cal(l,j,i); return ; } int mid=(l+r)>>1; if(p<=mid) update(lson,i,p); else update(rson,i,p); push_up(l,r,rt,i); } void gcd(int a,int b,int& d,int& x,int& y){ if(!b) {d=a; x=1; y=0;} else {gcd(b,a%b,d,y,x); y-=x*(a/b);} } int inv(int a,int n){ int d,x,y; gcd(a,n,d,x,y); return d==1 ? (x+n)%n:-1; } int w[4]; void init(){ rep(i,4) w[i]=M/m[i]; rep(i,4) { w[i]=w[i]*inv(w[i]%m[i],m[i]); } } int kase=1,n; main() { init(); int T; scanf("%d",&T); while(T--){ int Q; scanf("%d %d",&n,&Q); for(int i=1;i<=n;i++) read(i); rep(i,4) { build(1,n,1,i); } printf("Case #%d: ",kase++); while(Q--){ int cmd,x,y; scanf("%d %d",&cmd,&x); if(cmd==1){ int ans=0; rep(i,4) ans=(ans+w[i]*sum[1][i][x%m[i]])%M; printf("%d ",ans); } else{ read(x); rep(i,4) update(1,n,1,i,x); } } } }

热门文章