题意： 定义将一个\(t\)如下转换成一个二元组：\[ f(t) = \begin{cases} x = (t + \left\lfloor \frac{t}{B} \right \rfloor) \bmod A\\ y = t \bmod b \end{cases} \] 询问\([l_i, r_i]\)之间的\(t_i\)能够转换成多少个本质不同的二元组。
思路： 考虑\((x_1, y_1)\)和\((x_2, y_2)\)相同的时候：\[ \begin{cases} t_1 + \left\lfloor \frac{t_1}{B} \right\rfloor &\equiv& t_2 + \left \lfloor \frac{t_2}{B} \right\rfloor \bmod A \\ t_1 &\equiv& t_2 \bmod B \end{cases} \] 我们不妨令\(t_1 = t_2 + kB\)，代入第一个式子有：\[ \begin{eqnarray*} t_2 + kB + \left\lfloor \frac{t_2 + kB}{B} \right \rfloor \equiv t_2 + \left \lfloor \frac{t_2}{B} \right \rfloor \bmod A \end{eqnarray*} \] 化简之后有：\[ \begin{eqnarray*} k(B + 1) \equiv 0 \bmod A \end{eqnarray*} \] 所以有\(A\;|\;k(B + 1)\)，继而有\(\frac{A}{gcd(A, B + 1)}\;|\;k\)，令\(g = \frac{A}{gcd(A, B + 1)}\)，那么有\(g\;|\;k\)。 所以\(k\)要满足是\(g\)的倍数上述条件才成立，而\(t_1\)模\(B\)的个数是\(B\)个，所以循环节长度为\(T = gB\)。 将区间取模之后变成一条条线段，差分得到\([0, T)\)的覆盖区间长度即为答案。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 1000010 #define pll pair <ll, ll> #define fi first #define se second int n; ll l[N], r[N]; ll A, B; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } multiset <pll> se; void add(ll l, ll r) { se.insert(pll(l, 1)); se.insert(pll(r + 1, -1)); } int main() { while (scanf("%d%lld%lld", &n, &A, &B) != EOF) { se.clear(); ll sum = 0; for (int i = 1; i <= n; ++i) { scanf("%lld%lld", l + i, r + i); sum += r[i] - l[i] + 1; } ll g = gcd(A, B + 1); if (1.0 * A * B / g > 1e18) { printf("%lld\n", sum); continue; } ll T = A / g * B; for (int i = 1; i <= n; ++i) { if (r[i] - l[i] + 1 >= T) { printf("%lld\n", T); return 0; } l[i] %= T; r[i] %= T; if (l[i] > r[i]) { add(l[i], T - 1); add(0, r[i]); } else { add(l[i], r[i]); } } ll base = 0, lst = -1, res = 0; for (auto it : se) { if (base > 0) res += it.fi - lst; base += it.se; lst = it.fi; } printf("%lld\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11148764.html
相关资源：JAVA上百实例源码以及开源项目