同余方程组解的个数 （hdu1573）

2019-04-14 21:18发布

站内文章 / 模拟电子
10311 0 1099

                        由此入门
  • 同余方程组（模非互质）可以通过合并方程求解。
  •         假设以上都知道的。或者点击打开链接
  • 通过以上方法求得最小正整数解x 方程组的模底为lcm=LCM(a1,a2...an) 
  •     通解：  
  •     有解：  
  •     无解：  
  • 注意：有解时，若a=0 则t=0去除，题目要求正整数。
#include #define ll long long int x,y; int d; int A[20]; int B[20]; void exgcd(int a,int b){ if(b==0){ d=a; x=1; y=0; return ; } exgcd(b,a%b); int t=x; x=y; y=t-(a/b)*y; } int mod(int x,int n){ return (x%n+n)%n; } //x=b[i](mod c[i]) ll equation(int b[],int c[],int n){ for(int i=1;iN)printf("0 "); else { //x+lcm*t<=N ll lcm=1; for(int i=0;i

热门文章