今天一早晨都花在这题上了,昨天晚上看了一晚上终于把数论回忆了一下
思路:解模不互质的线性同余方程组,wa了一早晨不知道哪里错了,估计是所有数的lcm求错了???不解,后来没有独立的求lcm,而是用合并方程的最后一个lcm
就AC了,(主要是一开始没想到用这个。。。还另外求,智商拙计啊)
code:
#include <iostream> #include <cstdio> #include <cstring> #define LL __int64 using namespace std; LL extend_gcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1; y=0; return a; } LL gcd=extend_gcd(b,a%b,x,y); LL t=x; x=y; y=t-(a/b)*y; return gcd; } LL m[20],r[20]; void solve(LL t,int n) { int i; LL m1,m2,r1,r2,x,y,tmp,gcd; bool flag=0; m1=m[1]; r1=r[1]; for(i=2;i<=n;i++) { m2=m[i]; r2=r[i]; gcd=extend_gcd(m1,m2,x,y); if((r2-r1)%gcd) { flag=true; break; } x = x*(r2-r1)/gcd; //转换最小正整数解 tmp = m2/gcd; x = ( x%tmp + tmp ) % tmp; //合并为一个同余方程 r1 = x*m1+r1; m1 = m1*m2/gcd; } if(flag || t<r1) { puts("0"); }else{ printf("%I64d\n",(t-r1)/m1+1-(r1==0?1:0)); } } int main() { //freopen("input.txt","r",stdin); int n,i; LL cas,lcm,lim,x,y; scanf("%I64d",&cas); while(cas--) { lcm=1; scanf("%I64d%d",&lim,&n); for(i=1;i<=n;i++) { scanf("%I64d",&m[i]); } for(i=1;i<=n;i++) { scanf("%I64d",&r[i]); } solve(lim,n); } return 0; }