每日一题：Yet Another Counting Problem

题意

给你两个数 $a$ 和 $b$，$q$ 次询问 $[l,r]$ 内满足 (($x$ mod $a$) mod $b$) != (($x$ mod $b$) mod $a$) 的 $x$ 个数。（$q<=500,1<=a,b<=200,1<=l<=r<=1e18$）

solution

若 x % a % b != x % b % a，则(x + a $\times$ b ) % a % b != (x + $a \times b$ ) % b % a. 可以得到规律一定是以 a $\times$ b 为循环的，因此预处理前 a $\times$ b个即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll t, a, b, q, l, r, sl, sr, sum[N];
int main() {
  cin >> t;
  while (t--) {
    cin >> a >> b >> q;
    int p = a * b;
    for (int i = 1; i < p; i++) sum[i] = sum[i - 1] + (i % a % b != i % b % a);
    while (q--) {
      cin >> l >> r;
      l--;
      sl = l / p * sum[p - 1] + sum[l % p];
      sr = r / p * sum[p - 1] + sum[r % p];
      cout << sr - sl << ' ';
    }
    cout << '\n';
  }
  return 0;
}