题目链接

LOJ3144
LuoguP5444

题目概括

给定 $n$ 个不相交的区间 $[l_i,r_i]$ 和 $A$ 和 $B$。

定义一个数 $t$ 到另一个二元组的映射为 $t\rightarrow ((t+\lfloor \frac tB\rfloor) \; mod \; A,t \; mod \; B)$

问这些区间的并中所有数的映射中不同的二元组有多少个。

数据范围:$N\leq 10^6,A,B,l_i,r_i\leq 10^{18}$

思路要点

考虑循环节大小,设循环节长度为 $S$,二元组分别为两个函数表示

$$ x(t)=(t+\lfloor \frac tB\rfloor) \; mod \; A $$

$$ y(t)=t \; mod \; B $$

$$ x(t+S)=(t+S+\lfloor \frac {t+S}B\rfloor) \; mod \; A $$

$$ y(t+S)=(t+S) \; mod \; B $$

$$ t\equiv t+S \mod B $$

显然

$$ S\mod B=0 $$

那么令$S=kB$

$$ x(t+kB)\equiv (t+\lfloor \frac tB\rfloor+kB+k)\mod A $$

$$ k(B+1)\mod A=0 $$

显然

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

循环节大小为

$$ B\cdot \frac A{\text{gcd}(B+1,A)} $$

然后就是离散化后线段覆盖即可

时间复杂度 $\Theta(nlogn)$

代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 2e6 + 5;

ll A, B, cir, ans; 
int n, tot;
pair<ll, ll> sec[N];

template <class T> 
T gcd(T x, T y) {
  return !y ? x : gcd(y, x % y); 
}

ll calc(ll x) {
  return x % cir ? x % cir : cir; 
}

int main() {
  scanf("%d %lld %lld", &n, &A, &B);
  cir = A / gcd(A, B + 1);
  if (3e18 / cir < B) 
    cir = 3e18;
  else 
    cir *= B;
  tot = n;  
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &sec[i].first, &sec[i].second);
    if (sec[i].second - sec[i].first + 1 >= cir) {
      printf("%lld\n", cir);
      return 0;
    }
    sec[i] = make_pair(calc(sec[i].first), calc(sec[i].second));
    if (sec[i].first > sec[i].second) {
      sec[++tot] = make_pair(sec[i].first, cir);
      sec[i] = make_pair(1, sec[i].second);
    }
  }
  sec[++tot] = make_pair(cir + 1, cir);
  sort(sec + 1, sec + 1 + tot);
  ll left = sec[1].first, right = sec[1].second;
  for (int i = 2; i <= tot; i++) {
    if (sec[i].first <= right) {
      right = max(right, sec[i].second);
    } else {
      ans += right - left + 1; 
      left = sec[i].first, right = sec[i].second;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

后言

  • 对于数据较大,这题目又存在模运算,所以题目的突破口一定是找循环节。
最后修改:2020 年 04 月 01 日 09 : 20 PM
如果觉得我的文章对你有用,请随意赞赏