#define DEBUG
// #define FASTIO
#include <cstring>
#include <cassert>
#include <utility>
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <tuple>
#include <climits>
#include <limits>
#include <deque>
#include <list>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <complex>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#define F first
#define S second
#define pb push_back
#define endl "\n"
#ifdef FASTIO
#define pr(x) printf("%d", x)
#define ps printf(" ")
#define endc printf("\n")
#define pl(x) printf("%lld", x)
#define pf(x) printf("%lf", x)
#define sc(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define sf(x) scanf("%lf", &x)
#define IOS
#endif
#ifndef FASTIO
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); }
#endif
#ifdef DEBUG
#define dbg(s) {s;}
#endif
#ifndef DEBUG
#define dbg(s)
#endif
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { // from [0, n-1]
return uniform_int_distribution<int>(0, x - 1)(rng);
}
#define int ll
#define i32 int32_t
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
inline string ps(pii z) {
stringstream ss; ss << "[" << z.F << ", " << z.S << "]";
return ss.str();
}
ll gcd(ll x, ll y) {
if (x < y) return gcd(y, x);
if (y == 0) return x;
return gcd(y, x % y);
}
const ll mod = 1e9 + 7;
ll modexp(ll x, ll ex) {
ll ans = 1ll;
while (ex > 0) {
if (ex & 1ll) ans = (ans * x) % mod;
ex >>= 1ll;
x = (x * x) % mod;
}
return ans;
}
const int maxn = 1e6 + 7;
const ll inf = 1e18 + 7;
vector < pii > v;
i32 main() {
//freopen("<file>.in", "r", stdin);
//freopen("<file>.out", "w", stdout);
IOS;
int n, A, B; cin >> n >> A >> B;
int g = gcd(A, B + 1); A /= g;
if (A >= inf / B) A = inf;
else A *= B;
for (int j = 1; j <= n; j++) {
int l, r; cin >> l >> r;
if (r - l >= A) {
cout << A << endl; return 0;
}
if (l <= A * (r / A)) {
v.pb({0, r % A});
if (l < A * (r / A))
v.pb({l % A, A - 1});
} else {
v.pb({l % A, r % A});
}
}
sort(all(v));
int ans = 0;
for (int j = 0; j < v.size(); ) {
int i = j; pii ci = v[j];
while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
i++; ci.S = max(ci.S, v[i].S);
}
j = i + 1;
ans += ci.S - ci.F + 1;
}
cout << ans << endl;
}
Compilation message
strange_device.c:4:10: fatal error: cstring: No such file or directory
#include <cstring>
^~~~~~~~~
compilation terminated.
