题解-APIO2019奇怪装置

problem

题意概要：设函数 \(f(t)\) 的返回值为一个二元组，即 \(f(t)=((t+\lfloor \frac tB\rfloor)\bmod A, t\bmod B)\)，现在给出 \(n\) 个区间，问 \(t\) 在这 \(n\) 个区间中取值时，有多少个不同的 \(f(t)\)。

\(n\leq 10^6,\ l_i,r_i,A,B\leq 10^{18}\)，区间互不相交

Solution

一开始没啥想法，\(loj\) 的题面上写了 \(l_i\leq r_i,r_i<l_i+1\)……这不就是说 \(l_i=r_i\) 嘛！暴力 \(O(n)\) 就好了！

实际上是 \(r_i<l_{i+1}\)，然后看着 \(5\) 分一档的部分分陷入了沉思……后来直接想正解发现正解比暴力容易……

由于不同的二元组难以考虑，考虑两个二元组相同的情况（即 \(f(t_1)=f(t_2)\)）。同时这个二元组中的两个函数中，第二维较为简单，考虑从这一维下手。

由于第二维要相同，所以两个相同二元组一定是 \(f(x)\) 与 \(f(x+kB)\) 形式的，再考虑第一维：

\[x+\lfloor \frac xB\rfloor \equiv x+kB+\lfloor \frac {x+kB}B\rfloor \pmod A\\
x+\lfloor \frac xB\rfloor \equiv x+\lfloor \frac xB\rfloor +kB+k \pmod A\\
k(B+1)\equiv 0\pmod A
\]

又由于满足 \(k(B+1)\equiv 0\pmod A\) 的最小 \(k=\frac A{\gcd\{A,B+1\}}\)

即满足 \(f(x)=f(y)\) 的，一定满足 \(\frac {AB}{\gcd \{A,B+1\}}|(y-x)\)。换种说法，也即 \(x\equiv y\pmod {\frac {AB}{\gcd\{A,B+1\}}}\)。

问题转化为在模 \(\frac {AB}{\gcd\{A,B+1\}}\) 意义下的覆盖区间长度，时间复杂度 \(O(n\log n)\)。

Code

//loj-3144

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <typename _tp> inline void read(_tp&x){

	char ch=getchar();x=0;while(!isdigit(ch))ch=getchar();

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

}

inline ll gcd(ll A, ll B) {return B ? gcd(B, A%B) : A;}

const int N = 2001000;

typedef pair <ll,int> pli;

pli a[N];

int n, tot;

ll A, B;

int main() {

	read(n), read(A),read(B);

	ll d = A / gcd(A, B+1);

	ll l, r, l0, l1, r0, r1;

	bool flg = false;

	if(1e18 / B < d) {

		for(int i=1;i<=n;++i) {

			read(l), read(r);

			a[++tot] = pli(l, +1);

			a[++tot] = pli(r+1, -1);

		}

		flg = true;

	} else {

		d *= B;

		for(int i=1;i<=n;++i) {

			read(l), l0 = l % d, l1 = l / d;

			read(r), r0 = r % d, r1 = r / d;

			if(l1 == r1) {

				a[++tot] = pli(l0, +1);

				a[++tot] = pli(r0+1, -1);

			} else if(l1 + 1 == r1) {

				a[++tot] = pli(l0, +1);

				a[++tot] = pli(0, +1);

				a[++tot] = pli(r0+1, -1);

			} else return printf("%lld\n", d), 0;

		}

	}

	if(!flg) a[++tot] = pli(d, 0);

	a[0] = pli(0, 0);

	sort(a+1, a+tot+1);

	int vl = 0;

	ll Ans = 0ll;

	for(int i=1;i<=tot;++i) {

		if(vl) Ans += a[i].first - a[i-1].first;

		vl += a[i].second;

	}

	printf("%lld\n", Ans);

	return 0;

}

巴特西

题解-APIO2019奇怪装置

problem

Solution

Code

最新文章

热门文章