奇怪装置「APIO 2019」(推柿子+求区间并)

chedan

看一眼题,感觉题目描述的不是很清楚啊。对于每段时间到底是从头开始算还是从时间开始算啊?

看一眼样例发现是从头开始算。

然后推了一波式子在最后一步脑抽了一下就没推出来/kk。

题目描述

考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕,分别显示两个整数 \(x\) 和 \(y\)。

经过研究,科学家对该装置得出了一个结论:该装置是一个特殊的时钟,它从过去的某个时间点开始测量经过的时刻数 \(t\),但该装置的创造者却将 \(t\) 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 \(t\),装置会显示两个整数:\(x = ((t + \lfloor \frac{t}{B} \rfloor) \bmod A)\),与 \(y = (t \bmod B)\)。这里 \(\lfloor x\rfloor\) 是下取整函数,表示小于或等于 \(x\) 的最大整数。

考古学家通过进一步研究还发现,该装置的屏幕无法一直工作。实际上,该装置的屏幕只在 \(n\) 个连续的时间区间段中能正常工作。第 \(i\) 个时间段从时刻 \(l_i\) 到时刻 \(r_i\) 。现在科学家想要知道有多少个不同的数对 \((x, y)\) 能够在该装置工作时被显示出来。

两个数对 \((x_1, y_1)\) 和 \((x_2, y_2)\) 不同当且仅当 \(x_1 \not = x_2\) 或 \(y_1 \not = y_2\) 。

对于全部数据,\(1\le n\le 10^6,1\le A,B\le 10^{18},0\le l_i\le r_i\le 10^{18},r_i<l_{i+1}\)

Analysis

看到取模所以这种东西多半是有循环节的。

打一打表也不难发现它有循环节。

而循环节是从 \((0,0)\) 开始的所以一定是在下一个 \((0,0)\) 前结束。这打表也可以看出来。

我一开始打算打表找规律,然后发现这东西有的时候是\(AB\),有的时候是\(AB/2\),有的时候还直接就是\(B\)。嗯...不可做。

不过在打表的过程中我找到了其中一个规律:循环节 \(T\) 是 \(B\) 的倍数(这不废话吗)。

之后我又对所有 \(B\) 的倍数的 \(x\) 值打表,试图找规律,无果。

教练讲了一下:解决 \(T + \lfloor\frac{T}{B}\rfloor \equiv 0 (\bmod A)\) 即可。

我:可是这有个取整符号很不好搞。

教练:你不是推出来\(B|T\)了吗?

我:!@#¥%……&*

然后推一波柿子:

设 \(T=Bk\)

有\(Bk + \lfloor\frac{Bk}{B}\rfloor = Bk + k \equiv 0(\bmod A)\)

\(k(B+1)=sA\)

\(k=\frac{sa}{B+1}\)

求最小的\(s\)使得\(k\)是整数

显然\(s=\frac{B+1}{gcd(A,B+1)}\)

\(k=\frac{A}{gcd(A,B+1)}\)

\(T=\frac{AB}{gcd(A,B+1)}\)

求出循环节\(T\)后就是个区间并问题了,明天再来补。

上一篇:SP26108 TRENDGCD - Trending GCD


下一篇:AGC041