#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
typedef __int128 i128;
const ll inf=1e18+5;
void solve(){
ll n, a, b;
cin>>n>>a>>b;
vector<pll> v(n);
for(auto &[x, y]:v){
cin>>x>>y;
}
ll tep=(b%a+1)%a;
i128 mod;
if(tep==0){
mod=b;
}
else{
mod=a/__gcd(a, tep);
mod*=b;
}
if(mod>(i128) inf){
ll ans=0;
for(auto &[x, y]:v){
ans+=y-x+1;
}
cout<<ans<<'\n';
return;
}
vector<pll> dumb;
for(auto &[x, y]:v){
if(y-x+1>=mod){
cout<<(ll) mod<<'\n';
return;
}
ll f=x%mod;
ll s=y%mod;
if(f>s){
dumb.pb({f, mod-1});
dumb.pb({0, s});
}
else{
dumb.pb({f, s});
}
}
sort(dumb.begin(), dumb.end());
ll ans=0;
ll mx=-1;
for(auto &[x, y]:dumb){
if(y>mx){
ans+=min(y-x+1, y-mx);
mx=y;
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |