Modified LCS

 1 /*****************
 2 f1+(k1-1)*d1=f2+(k2-1)*d2
 3 =>  (k1-1)*d1+(k2-1)*(-d2)=f2-f1;
 4 =>  d1*x+y*(-d2)=f2-f1   d1=>[0,n1-1]  d2=>[0,n2-1]
 5 求在给定范围内解的个数
 6 *********************/
 7 #include"iostream"
 8 #include"cstdio"
 9 #include"cstring"
10 #include"cmath"
11 #include"algorithm"
12 using namespace std;
13 typedef long long ll;
14 void exgcd(ll n,ll m,ll &x,ll &y,ll &d)
15 {
16     if(!m){
17         x=1;y=0;d=n;
18     }
19     else{
20         exgcd(m,n%m,y,x,d);
21         y-=(n/m)*x;
22     }
23 } 
24 int main()
25 {
26     ll f1,n1,d1,f2,n2,d2,i,j,t;
27     cin>>t;
28     while(t--)
29     {
30         ll x,y,tmp,d;
31         //cin>>n1>>f1>>d1>>n2>>f2>>d2;
32         scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
33         exgcd(d1,-d2,x,y,d);
34         f2-=f1;
35         if(f2%d){
36             //cout<<"0"<<endl;
37             puts("0");
38             continue;
39         }
40         x=x*(f2/d);
41         y=y*(f2/d);
42         //接下来  逼近[0,n1-1],[0,n2-1] 
43         ll t1=d2/(abs(d));
44         ll t2=d1/(abs(d));
45         if(x<0||y<0)
46         {
47             int i=1;
48             while(1)
49             {
50                 if(x+t1*i>=0&&y+t2*i>=0)
51                     break;
52                 i++;
53             }
54             x=x+t1*i;
55             y=y+t2*i;
56         }
57         else
58         {
59             int i=1;
60             while(1)
61             {
62                 if(x-t1*i<0||y-t2*i<0)
63                     break;
64                 i++;
65             }
66             x=x-t1*(i-1);
67             y=y-t2*(i-1);    
68         }
69         if(x>(n1-1)||y>(n2-1))
70         {
71             //cout<<"0"<<endl;
72             puts("0");
73             continue;
74         }
75         int ans=1;
76         while(1)
77         {
78             if(x+t1*ans>(n1-1)||y+t2*ans>(n2-1))
79                 break;
80             ans++;
81         }
82         cout<<ans<<endl;
83         //printf("%lld\n",ans);
84     }
85     return 0;
86 }