HNU2[J题]Modified LCS 扩展GCD

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12831&courseid=268

解题思路：求出最小的两个为正且相等的下标（利用扩展GCD），然后就可以直接求了。

解题代码：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <stack>
10 #include <list>
11 #include <vector>
12 using namespace std;
13 #define LL __int64
14 LL x,y,gcd;
15 void exgcd(LL a ,LL b)
16 {
17     if (!b)
18     {
19         x=1;
20         y=1;
21         gcd=a;
22         return;
23     }
24     exgcd(b,a%b);
25     LL t=x;
26     x=y;
27     y=t-a/b*y;
28     return ;
29 }
30 int main()
31 {
32     int T;
33     LL n1,n2,f1,f2,d1,d2;
34 //    freopen("in.txt", "r", stdin);
35 //    freopen("outt.txt","w",stdout);
36     scanf("%d",&T);
37     while (T--)
38     {
39         cin>>n1>>f1>>d1>>n2>>f2>>d2;
40         LL f=f2-f1;
41         exgcd(d1,-d2);
42         if (f % gcd)
43         {
44             puts("0");
45             continue;
46         }
47         else
48         {
49             LL r=abs((-d2)/gcd);
50             x=(x*f/gcd % r+r)%r;
51             y=(f-x*d1)/(-d2);
52             LL dx=abs(d1/gcd);
53             LL dy=abs(d2/gcd);
54             LL ans=min((n1-x-1)/dy,(n2-y-1)/dx)+1;
55             //if (ans<0) ans=0;
56             cout<<ans<<endl;
57         }
58     } 
59     return 0;
60 }

View Code

没有梦想，何谈远方