#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
vector <pair<ll,ll>> v;
ll l[1000005],r[1000005];
ll gcd (ll a, ll b){
if (b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a, ll b){
return a/gcd(a,b)*b;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>a>>b;
ll t=1000005;
ll x;
// if ((b+1)%a==0){
// if (b>1000005){
// t=1000005;
// }
// else
// t=b;
// }
// else{
// if (b>1000005||a>1000005||a*b>1000005){
// t=1000005;
// }
// else
// t=a*b;
// }
// cout<<t;
for (int i=b;i<=1000005;i+=1){
v.push_back({(i+i/b)%a,i%b});
if((i+(i/b))%a==0&&i%b==0){
t=i;
break;
}
// cout<<i<<endl;
}
t=lcm(t,b);
// cout<<t;
set <pair<ll,ll>> st;
for (int i=1;i<=n;i++){
cin>>l[i]>>r[i];
ll u=r[i]-l[i]+1;
if (u>=t){
l[i]=0;
r[i]=t-1;
}
else{
ll q=r[i]-l[i];
ll p=l[i]%t;
l[i]=p;
r[i]=l[i]+q;
}
if (r[i]<=t-1){
st.insert({l[i],r[i]});
// cout<<l[i]<<" "<<r[i]<<endl;
}
else{
st.insert({l[i],t-1});
// cout<<l[i]<<" "<<t-1<<endl;
st.insert({0,(u-(t-l[i]))-1});
// cout<<0<<" "<<(u-(t-l[i]))-1<<endl;
}
// cout<<l[i]<<" "<<r[i]<<endl;
}
vector <pair<ll,ll>> pasang;
for (auto z:st){
pasang.push_back(z);
// cout<<z.first<<" "<<z.second<<endl;
}
sort(pasang.begin(),pasang.begin()+n);
vector <pair<ll,ll>> jawab;
ll last=pasang[0].second,previous=pasang[0].first;
pasang.push_back({(ll)1e18+100,(ll)1e18+100});
// sort(pasang.begin(),pasang.end());
for (int i=1;i<pasang.size();i++){
if (pasang[i].first<=last){
last=max(last,pasang[i].second);
}
else{
jawab.push_back({previous,last});
previous=pasang[i].first;
last=max(last,pasang[i].second);
}
}
// if (previous>jawab[jawab.size()-1].second){
// // jawab.push_back({previous,last});
// }
ll ans=0;
set<pair<ll,ll>> s;
for (int i=0;i<jawab.size();i++){
for (int j=jawab[i].first;j<=jawab[i].second;j++){
s.insert(v[j]);
}
cout<<s.size();
// cout<<jawab[i].first<<" "<<jawab[i].second<<":::"<<endl;
}
cout<<" "<<s.size();
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=1;i<pasang.size();i++){
| ~^~~~~~~~~~~~~~
strange_device.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i=0;i<jawab.size();i++){
| ~^~~~~~~~~~~~~
strange_device.cpp:18:8: warning: unused variable 'x' [-Wunused-variable]
18 | ll x;
| ^
strange_device.cpp:93:8: warning: unused variable 'ans' [-Wunused-variable]
93 | ll ans=0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
