1003 - Copy
给你一个序列,每次给一个区间 $[l.r]$,把这个区间复制一份,插入到这段区间的后面,多次询问下标为 $x$ 的数字是几,答案是所有询问的异或值。
$1\le T \le 10, \sum n, \sum q\le 10^5$,复制区间的次数不超过 $20000$。
挖掘一些性质:
- 容易发现一次修改操作之后,如果询问的位置 $x \le r$,那么这个修改对查询没有影响。
-
如果某两次查询,恰巧对应的是同一个数,答案又是异或值,那么答案不变。
-
如果询问的位置 $ 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;
}