首页 > 代码库 > 【hdu 1573】X问题（数论--拓展欧几里德 求解同余方程组的个数 模版题）
【hdu 1573】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)。
解法：先同上题一样用拓展欧几里德求出同余方程组的最后一个方程 X=ax+b，再调整 x 来求得 X 的解的个数。一些解释请看下面的代码。
注意——每次联立方程后求最小正整数解，可以提高代码速度。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 typedef long long LL; 7 8 int n,m; 9 LL aa[12],bb[12];10 11 LL mabs(LL x) {return x<0?x:-x;}12 LL exgcd(LL a,LL b,LL& x,LL& y)13 {14 if (!b) {x=1,y=0; return a;}15 LL d,tx,ty;16 d=exgcd(b,a%b,tx,ty);17 x=ty,y=tx-(a/b)*ty;18 return d;19 }20 int main()21 {22 int T;23 scanf("%d",&T);24 while (T--)25 {26 scanf("%d%d",&n,&m);27 for (int i=1;i<=m;i++) scanf("%I64d",&aa[i]);28 for (int i=1;i<=m;i++) scanf("%I64d",&bb[i]);29 LL a,b,d,x,y;30 bool ok=false;31 a=aa[1],b=bb[1];32 for (int i=2;i<=m;i++)33 {34 d=exgcd(a,aa[i],x,y);//ax-aa[i]y=bb[i]-b35 if ((bb[i]-b)%d!=0) {ok=true;break;}36 x=x*((bb[i]-b)/d);37 38 LL t=mabs(aa[i]/d);39 x=(x%t+t)%t;40 41 b=a*x+b,a=a*aa[i]/d;//lcm(a,aa[i]);42 }43 if (ok) printf("0\n");44 else45 {46 LL ans=(b%a+a)%a,cnt=0;//X=ax+b 此时的ans为X的最小非负整数解47 if (ans>0 && ans<=n) cnt++;//若ans为合乎条件的X值才计入cnt48 cnt+=(n-ans)/a;//除ans以外的X的解的个数49 printf("%I64d\n",cnt);50 }51 }52 return 0;53 }
【hdu 1573】X问题（数论--拓展欧几里德 求解同余方程组的个数 模版题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。