26 暑假模拟赛补题1

前言

挺早的一场模拟赛了，我已经忘了当时的思考过程了，我看 T1 T2 我当时过了就不写了，发现 T3 现在重新看还不会，这太搞笑了，写一篇博客吧。

正文

给定正整数 \(N\)。
AA 有 \(X\) 个互不相交的在线区间 \([a_i,b_i]\)，BA 有 \(Y\) 个互不相交的在线区间 \([c_j,d_j]\)。

选择一个正整数 \(T\)（\(1 \le T \le N\)），则：

• AA 在时刻 \(T,3T,5T,\dots\)（不超过 \(N\)）发消息；
• BA 在时刻 \(2T,4T,6T,\dots\)（不超过 \(N\)）发消息。

如果 AA 的所有发消息时刻都在 AA 的在线区间内，且 BA 的所有发消息时刻都在 BA 的在线区间内，则称 \(T\) 合法。

求合法的 \(T\) 的数量。

• \(1 \le N \le 10^9\)
• \(1 \le X,Y \le 300\)
• 所有区间闭区间，且输入区间互不相邻：
  • \(a_{i+1} > b_i + 1\)
  • \(c_{j+1} > d_j + 1\)
• 所有区间端点均在 \([1,N]\) 内。

这个题给出了一些一堆限制，要求 \(T\) 满足所有限制（限制包括奇偶、且所有 \(kT\) 都在一个区间内），非常困难，所有我们考虑反过来找到一些不满足限制的 \(T\)，对于这些 \(T\) 出现的充要条件是存在一个区间 \([a,b]\)，其中 \([a,b]\) 是原区间的一个补集，有 \(kT \in [a,b]\)（要求 \(k\) 满足奇偶性限制）。

我们考虑改写一下这个式子，他会变成：

\[T \in [\lceil \frac{a}{k} \rceil,\lfloor \frac{b}{k} \rfloor] \]

我们发现这样子我们只需要枚举 \(k\) 得到一个区间的 \(T\) 不合法，然后求这些 \(T\) 的并集即可，发现这个区间竟然有整除，于是使用整除分块维护答案，这样子对于两种情况分讨一下 \(k\) 的取值，求出所有 \(T\) 不可选的区间，然后最后求个并集就做完了，时间复杂度是 \(\Theta((X+Y) \sqrt{N})\)。

#include<bits/stdc++.h>
using namespace std;int n,x,y;
vector<pair<int,int> > vx,vy,ans;void sol(vector<pair<int,int> > vec,int opt){vector<pair<int,int> > ve;if((*vec.begin()).first>1)ve.push_back(make_pair(1,(*vec.begin()).first-1));for(int i=1;i<int(vec.size());i++)ve.push_back(make_pair(vec[i-1].second+1,vec[i].first-1));if((*vec.end()).second<n)ve.push_back(make_pair((*--vec.end()).second+1,n));for(pair<int,int> i:ve){int a=i.first,b=i.second;
//		printf("a=%d,b=%d\n",a,b);for(int k=1;k<=n;k++){if(k%2!=opt)++k;if((a+k-1)/k>b/k)break;ans.push_back(make_pair((a+k-1)/k,b/k));int n1=(a+k-1)/((a+k-1)/k),n2=b/(b/k);k=min(n1,n2);}}return;
}int main(){
//	freopen("message.in","r",stdin);
//	freopen("message.out","w",stdout);scanf("%d",&n);scanf("%d",&x);for(int i=1;i<=x;i++){pair<int,int> tmp;scanf("%d%d",&tmp.first,&tmp.second);vx.push_back(tmp);}scanf("%d",&y);for(int i=1;i<=y;i++){pair<int,int> tmp;scanf("%d%d",&tmp.first,&tmp.second);vy.push_back(tmp);}sol(vx,1);
//	printf("??");sol(vy,0);sort(ans.begin(),ans.end());int lst=0,sum=0;for(pair<int,int> i:ans){
//		printf("l=%d,r=%d\n",i.first,i.second);sum+=max(0,i.second-max(i.first-1,lst));lst=max(lst,i.second);}printf("%d\n",n-sum);return 0;
}
/*
10000000
1
4092001 5033941
2
206 314
1214 10000000
*/
/*
2026.8.15
23:19-23:45
*/