#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#define pb push_back
#define int long long
#define str string
using namespace std;
const int M = 1e9 + 7;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, a, b;
cin >> n >> a >> b;
vector<pair<int, int>> pr(n);
for (int i = 0; i < n; i++) cin >> pr[i].first >> pr[i].second;
int g = gcd(a, b+1);
a /= g;
if (a * b >= 1e18+8800) {
int ans = 0;
for (auto p : pr) {
ans += p.second - p.first+1;
}
cout << ans;
return 0;
}
int num = a * b;
vector<pair<int, int>> ev;
for (auto p : pr) {
int l = p.first, r = p.second;
l %= num;
r %= num;
if (r < l) {
ev.pb({l, 1});
ev.pb({num, -1});
ev.pb({0, 1});
ev.pb({r+1, -1});
} else {
ev.pb({l, 1});
ev.pb({r+1, -1});
}
}
sort(ev.begin(), ev.end());
int bal = 0;
int last = 0;
int ans = 0;
for (auto p : ev) {
int x = p.first, type = p.second;
if (bal) {
ans += (x - last);
}
last = x;
bal += type;
}
cout << ans;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:36:13: error: 'gcd' was not declared in this scope
int g = gcd(a, b+1);
^~~
strange_device.cpp:36:13: note: suggested alternative: 'gcvt'
int g = gcd(a, b+1);
^~~
gcvt
