【LG5444】[APIO2019]奇怪装置
题面
题目大意：
给定(A,B)，对于(forall tin mathbb N)，有二元组((x,y)=((t+lfloorfrac tB floor)mod A,tmod B))。
对于给定的(n)个区间([l,r])，要你求出(tin [l_1,r_1]igcup [l_2,r_2]...igcup [l_n,r_n])对应有多少个不同的二元组。
数据范围：
(1leq nleq 10^6,1leq A,Bleq 10^{18},0leq l_ileq r_ileq 10^{18})。
题解
你首先要考虑到这种问题是有个循环节的 否则就会像我一样得到10分
设(t_1<t_2)所对应的二元组完全相同，那么
[egin{cases}
t_1+lfloorfrac{t_1}{B}
floor equiv t_2 + lfloor frac{t_2}{B}
floor(mod A)\
t_1equiv t_2(mod B)
end{cases}
]
那么根据第二个条件，我们不妨令$$t_1+kB=t_2,kin mathbb N$$
那么带到第一个式子中就是：
[t_1+lfloorfrac{t_1}{B}
floorequiv t_1+kB+k+lfloorfrac{t_1}{B}
floor(mod A)
]
化简得：$$k(B+1)equiv 0(mod A)$$
( herefore frac{A}{gcd(A,B+1)}|k)，即(k)最小为(frac{A}{gcd(A,B+1)})。
那么循环节(T=kB=frac{AB}{gcd(A,B+1)})。
然后对于所有([l,r])就可以转化为线段覆盖了，想怎么维护都行。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
inline ll gi() {
register ll data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e6 + 5;
ll N, A, B, l[MAX_N], r[MAX_N], T, ans;
multiset<pair<ll, int> > st;
void Add(ll l, ll r) { st.insert(make_pair(l, 1)), st.insert(make_pair(r + 1, -1)); }
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
N = gi(), A = gi(), B = gi(); ll d = __gcd(A, B + 1), sum = 0;
for (int i = 1; i <= N; i++) l[i] = gi(), r[i] = gi(), sum += r[i] - l[i] + 1;
if (1.0 * A / d * B > 1e18) return printf("%lld
", sum) & 0;
T = A / d * B;
for (int i = 1; i <= N; i++) {
if (r[i] - l[i] + 1 >= T) return printf("%lld
", T) & 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]);
}
st.insert(make_pair(T, 0));
ll lst = -1, c = 0;
for (auto it : st) {
if (c > 0) ans += it.first - lst;
c += it.second, lst = it.first;
}
printf("%lld
", ans);
return 0;
}