hdu 1573 X问题

时间:2023-01-17 15:40:48

  数论题,本想用中国剩余定理,可是取模的数之间不一定互质,用不了,看到网上有篇文章写得很好的:数论——中国剩余定理(互质与非互质),主要是采用合并方程的思想:

hdu 1573 X问题

  大致理解并参考他的代码后便去试试hdu上这道题,可还是wa了数遍。

 #include<cstdio>
#define scd(x) scanf("%d",&x)
#define sclld(x) scanf("%I64d",&x)
#define prd(x) printf("%d\n",x)
#define For(i,s,t) for(int i=s; i<t; ++i)
typedef long long LL; LL gcd(LL a, LL b) { return b==? a: gcd(b,a%b); }
LL lcm(LL x, LL y) { return x/gcd(x,y)*y; } void gcd(LL a, LL b, LL &d, LL &x, LL &y){
if(!b) { d=a; x=; y=; }
else { gcd(b,a%b,d,y,x); y-= x*(a/b); }
} LL inv(LL a, LL n){
LL d,x,y;
gcd(a,n,d,x,y);
return d==? (x+n)%n:-;
} bool merge(LL a1, LL n1, LL a2, LL n2, LL &aa, LL &nn){
LL d= gcd(n1,n2), c= a2-a1;
if(c%d) return ;
c= (c%n2+n2)%n2;
c/= d;
n2/= d;
c= c*inv(n1/d,n2)%n2;
c= c*n1+a1;
nn= n1*n2;
aa= (c%nn+nn)%nn;
return true;
} LL ext_china(LL len, LL a[], LL n[]){
LL a1= a[], n1= n[];
for(LL i=; i<len; ++i){
LL aa, nn;
if(!merge(a1,n1,a[i],n[i],aa,nn)) return -;
a1= aa;
n1= nn;
}
return (a1%n1+n1)%n1;
} LL a[], b[]; int main(){
int t;
LL n,m,M;
scd(t);
while(t--){
sclld(n); sclld(m);
M= ;
For(i,,m){
sclld(a[i]);
M= lcm(M,a[i]);
}
For(i,,m) sclld(b[i]);
LL tmp= ext_china(m,b,a);
if(tmp== -){
puts("");
continue;
}
int ans= ;
while(tmp<=n){
if(tmp) ++ans;
tmp+= M;
}
prd(ans);
}
return ;
}

  不想用cin,cout便用宏替换来代替输入输出了,有几个wa点:1.ext_china中有可能返回-1,要分开处理;2. tmp值一开始可能是0,不能算入最后结果中;3. M的值不能是a数组的简单相乘,应是它们的最小公倍数才对。

hdu 1573 X问题

hdu 1573 X问题hdu 1573 X问题