1003 - Copy

给你一个序列，每次给一个区间 $[l.r]$，把这个区间复制一份，插入到这段区间的后面，多次询问下标为 $x$ 的数字是几，答案是所有询问的异或值。

$1\le T \le 10, \sum n, \sum q\le 10^5$，复制区间的次数不超过 $20000$。

挖掘一些性质：

1. 容易发现一次修改操作之后，如果询问的位置 $x \le r$，那么这个修改对查询没有影响。

2. 如果某两次查询，恰巧对应的是同一个数，答案又是异或值，那么答案不变。

3. 如果询问的位置 $x > r$，考虑位置偏移了多少。当前 $x$ 上的数实际上是修改前 $x - (r - l + 1)$ 上的数。

发现修改的次数很少，提示我们可以离线。

考虑倒着处理所有操作。

• 如果是询问，我们把他的位置记下来，这个位置上的数将贡献答案。
• 如果是修改，我们之前存下来的所有询问的位置都要偏移 $r - l + 1$。

这样想是简单一些的，但是碰到修改的情况复杂度是 $n^2$ 的。由于所有坐标都是整体偏移，再根据性质 $2$，我们可以用一个 bitset 存储所有位置会不会被异或到答案里。

• 询问 $x$，将 $x$ 位 bit 异或 $1$。
• 修改 $[l, r]$，所有大于 $r$ 下标需要减少 $r - l + 1$，等价于将 $[r + 1, n]$ 的所有比特右移 $r - l + 1$。

最后我们只需要看哪些位置需要被异或进答案即可。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

const int B = 1e5 + 5;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; i++) {
      int opt, l, r;
      cin >> opt >> l;
      l--;
      if (opt == 1) {
        cin >> r;
        r--;
        queries[i] = {l, r};
      } else {
        queries[i] = {l, -1};
      }
    }
    reverse(queries.begin(), queries.end());
    bitset<B> dp;
    for (auto &query : queries) {
      int l = query.first, r = query.second;
      if (r == -1) {
        dp.flip(l);
      } else {
        int len = r - l + 1;
        auto x = dp & (~bitset<B>(0) >> (B - r - 1));
        auto y = dp & (~bitset<B>(0) << (r + 1));
        dp = x ^ (y >> (len));
      }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
      if (dp[i]) {
        ans ^= a[i];
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1009 - ShuanQ

加密过程：$e = raw \times P \pmod M$

解密过程：$raw = e\times Q\pmod M$，其中 $Q = P^{-1}, P\times Q \equiv 1 \pmod M,M 是质数$。

给你 $P, Q, e$，找到一个模数 $M(M > P, Q, e)$ 来解密。输出 $raw$，如果无法解密输出 “ShuanQ”。

也就是说找到一个 $M$ 使得 $P$ 在模 $M$ 意义下的逆元是 $Q$。$1 \leq P, Q, e \le 2 \times 10^6$

直接枚举 $M$ 算逆元会 T。

利用数论的一个结论：对于一个数 $n$ ，大于$\sqrt n$ 的质因子最多只有一个
$$P\times Q\equiv 1 \pmod M \\ P\times Q - 1 \equiv k\times M, k \ge 1$$
发现 $kM$ 是一个合数，$M$ 是 $kM$ 的一个质因子，且要满足 $M > P,Q$ 。所以我们筛 $P\times Q - 1$ 的质因子，比$P, Q, e$ 大的最多只有 $1$ 个，要不就没有。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int p, q, e;
    cin >> p >> q >> e;
    long long n = 1ll * p * q - 1, raw = -1;
    long long m = -1;
    for (long long i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        while (n % i == 0) {
          n /= i;
        }
        m = i;
      }
    }
    if (n > 1) m = n;
    if (m > max(p, q)) {
      cout << 1ll * e * q % m << '\n';
    } else {
      cout << "shuanQ\n";
    }
  }
  return 0;
}