首页 > 代码库 > 【HDU1573】X问题
【HDU1573】X问题
【题目描述】
求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。
【题解】
模板题,为读者提供一个中国剩余定理(非互质版)的模板
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 int T,n,s,M,ans,flag,a[15],m[15]; 10 inline int read() 11 { 12 int x=0,f=1; char ch=getchar(); 13 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} 14 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} 15 return x*f; 16 } 17 void exgcd(int a,int b,int &g,int &x,int &y) 18 { 19 if(b==0) {x=1; y=0; g=a; return;} 20 exgcd(b,a%b,g,x,y); 21 int t=x;x=y;y=t-a/b*y; 22 } 23 void China() 24 { 25 int A=a[1],k,y; M=m[1]; 26 for(int i=2;i<=n;i++) 27 { 28 int da=a[i]-A,g; 29 exgcd(M,m[i],g,k,y); 30 if(da%g) {flag=1; return;} 31 int t=m[i]/g; 32 k*=da/g; 33 k=(k+t)%t; 34 A+=k*M; 35 M=M*m[i]/g; 36 A=(A+M)%M; 37 } 38 ans=A; 39 } 40 int main() 41 { 42 freopen("cin.in","r",stdin); 43 freopen("cout.out","w",stdout); 44 T=read(); 45 while(T--) 46 { 47 s=read(); n=read(); flag=0; 48 for(int i=1;i<=n;i++) m[i]=read(); 49 for(int i=1;i<=n;i++) a[i]=read(); 50 China(); 51 if(ans>s||flag) {printf("0\n"); continue;} 52 int sum=(s-ans)/M+1; 53 if(ans==0) sum--; 54 printf("%d\n",sum); 55 } 56 return 0; 57 }
【HDU1573】X问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。