cf_ducational Codeforces Round 16

cf_ducational Codeforces Round 16_D（gcd）

题意：求R-L区间满足x=a1*k+b1=a2*l+b2的x的个数;

思路：求出最小的满足条件的x0，则ans=(L-x)/(a1/gcd(a1, a2)*a2)+1;

注意剪枝，不然会超时；

代码：

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define MAXN 100000+10
 4 using namespace std;
 5 
 6 ll get_gcd(ll a, ll b)
 7 {
 8     return b ? get_gcd(b, a%b) : a;
 9 }
10 
11 int main(void)
12 {
13     ll a1, b1, a2, b2, R, L;
14     cin >> a1 >> b1 >> a2 >> b2 >> R >> L;
15     ll k=ceil((R-b1)*1.0/a1), l=ceil((R-b2)*1.0/a2);
16     k=max(0ll, k), l=max(0ll, l);
17     ll x1=a1*k+b1, x2=a2*l+b2;
18 //    cout << x1 << " " << x2 << endl;//*******
19     if((b2-b1)%get_gcd(a1, a2)!=0)
20     {
21         cout << "0" << endl;
22         return 0;
23     }
24     if(a1==a2&&abs(x1-x2)<a1&&x1!=x2)
25     {
26         cout << "0" << endl;
27         return 0;
28     }
29 //    cout << x1 << " " << L << endl;//****
30     while(x1<=L && x2<=L && x1!=x2)
31     {
32         if(x1<x2)
33         x1+=max(1ll, (x2-x1)/a1)*a1;
34         else if(x1>x2)
35         x2+=max(1ll, (x1-x2)/a2)*a2;
36     }
37 //    cout << x1 << "**" << x2 << endl;//****
38     if(x1==x2&&x1>=R&&x1<=L)
39     cout << (L-x1)/(a1/get_gcd(a1, a2)*a2)+1 << endl;
40     else cout << "0" << endl;
41     return 0;
42 }

据说这题应该用拓展欧里几德解。。可惜我看了好久也没弄懂。。诶。。继续看吧。。。。