考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕，分别显示两个整数x和y。经过研究，科学家对该装置得出了一个结论：该装置是一个特殊的时钟，它从过去的某个时间点开始测量经过的时刻数t，但该装置的创造者却将t用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为t，装置会显示两个整数：\(x=((t+\lfloor\frac{t}{B}\rfloor)\mod A)\)，与\(y=(t\mod B)\)。这里⌊x⌋是下取整函数，表示小于或等于x的最大整数。考古学家通过进一步研究还发现，该装置的屏幕无法一直工作。实际上，该装置的屏幕只在n个连续的时间区间段中能正常工作。第i个时间段从时刻li到时刻ri。现在科学家想要知道有多少个不同的数对(x; y)能够在该装置工作时被显示出来。两个数对(x1; y1)和(x2; y2)不同当且仅当x1!=x2或y1!=y2。

打表发现循环节为\(\frac{AB}{\gcd(A,B+1)}\)，把区间膜一下求并即可

进行一个变换，假装 x 先不对A取模

让x-=y，发现 \(\lfloor\frac t B \rfloor *(B+1)\)，这时候新的xy和原来的xy一定是一一对应的，不证了

然后对t每B个分组，发现这b个里面x是一样的，y是0到b-1，也就是说在同一列

并且编号为i的组的横坐标为i*(B+1) //i就是t/B下取整，从0开始

然后我们再让x对A取模，就得到每组的循环节为\(\frac{A}{\gcd(A,B+1)}\)

由于一组有B个，所以整个循环节就出来了

考试时写的代码，由于考试时候机器32位不支持in128，就define了一下

#include <cstdio> #include <algorithm> using namespace std; // #define locale #ifdef locale typedef long long int128; #else typedef __int128 int128; #endif struct segment { long long l, r; } a[2000010]; int n; long long A, B, tot; long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); } bool cmp(const segment &a, const segment &b) { if (a.l != b.l) return a.l < b.l; return a.r < b.r; } int main() { scanf("%d%lld%lld", &n, &A, &B); int128 tmpmaxn = A / gcd(A, B + 1) * (int128)B; if (tmpmaxn > (int128)1000000000000000010LL) { long long ans = 0, tmpl, tmpr; for (int i = 1; i <= n; i++) { scanf("%lld%lld", &tmpl, &tmpr); ans += tmpr - tmpl + 1; } printf("%lld\n", ans); } else { long long maxn = tmpmaxn, tmpl, tmpr, idl, idr; for (int i = 1; i <= n; i++) { scanf("%lld%lld", &tmpl, &tmpr); idl = tmpl / maxn, idr = tmpr / maxn; if (idl == idr) a[++tot] = (segment){tmpl % maxn, tmpr % maxn}; else if (idl + 1 == idr) a[++tot] = (segment){tmpl % maxn, maxn - 1}, a[++tot] = (segment){0, tmpr % maxn}; else { printf("%lld\n", maxn); return 0; } } sort(a + 1, a + 1 + tot, cmp); long long totlen = 0, curl = a[1].l, curr = a[1].r; for (int i = 2; i <= tot; i++) { if (a[i].l > curr + 1) { totlen += curr - curl + 1; curl = a[i].l; curr = a[i].r; } else if (curr < a[i].r) { curr = a[i].r; } } totlen += curr - curl + 1; printf("%lld\n", totlen); } return 0; } 

讲真考试时候A了这道题吓了我这个蒟蒻一大跳

转载于:https://www.cnblogs.com/oier/p/10991769.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/98272740

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。