CF1034 div3
打了一下虚拟赛,感觉自己写代码不够认真,前面三个题都是能秒的,结果还寄了几发
这波直接写不会的题的题解吧,节省时间
F
题面
给定一个 \(n\) ,对于一个长度为 \(n\) 的排列,称满足下面条件的排列为好的
- 对于 \(1 < i \le n\) ,有 \(\gcd (i, a_i) > 1\)
求满足条件的排列中 \(a[i] = i\) 的个数最少的排列(固定个数),如果有多个,任意输出一个即可
\(2 \le n \le 10 ^ 5\)
题解
这道题在赛场上没有想到特别好的解决方法,后来看了看题解
这道题实际上就是让我们给不互质的两个数交换位置,并且如果能换,就一定要换
那么我们先考虑一件事,就是什么样的数是不能换的,其实就是它和排列里的其他数都互质,也就是 \(x \in pri ,2x > n\)
那如果 \(x \in pri,2x <= n\) 呢?那 \(x\) 是可以换的,并且只能和 \(2x,3x,\cdots\) 这几个数换
如果是这样,我们可以考虑每个数的最大质因子,将最大质因子相同的放在一组,然后顺次进行移位,完成交换,这样就能保证每个能交换的数一定会交换
为什么不能用最小质因子分组?因为如果用最小质因子分组,那么对于一个 \(x \in pri, 2x \le n\) ,它是无法交换的,因为 \(2x\) 被分到了最小质因子为 2 的一组,\(3x,4x,\cdots\) 也同理,所以我们要按照最大质因子分组,保证能换的都被换
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>using namespace std;namespace michaele {const int N = 2e5 + 10;int a[N], pri[N], v[N], cnt;vector <int> cycle;void primes (int n) {for (int i = 2; i <= n; i++) {if (!v[i]) {pri[++cnt] = i;v[i] = 1;}for (int j = 1; pri[j] * i <= n && j <= cnt; j++) {v[pri[j] * i] = 1;if (i % pri[j] == 0) break;}}}void solve () {int n;cin >> n;memset (a, 0, sizeof a);//倒序枚举质因子,确保每个数被分到最大质因子那一组for (int i = cnt; i >= 1; i--) {cycle.clear ();for (int j = pri[i]; j <= n; j += pri[i]) {if (!a[j]) {cycle.push_back (j);}}for (int j = 0; j < (int)cycle.size (); j++) {a[cycle[j]] = cycle[(j + 1) % cycle.size()];}}for (int i = 1; i <= n; i++) {if (!a[i]) a[i] = i;printf ("%d ", a[i]);}printf ("\n");}void main () {primes (1e5 + 10);int T;cin >> T;while (T--) solve ();}
}int main () {michaele :: main ();return 0;
}
G
题面
给定一个整数 \(m\) ( \(2\leq m\leq 5\cdot 10^5\) )和一个由小于 \(m\) 的非负整数组成的数组 \(a\) 。
回答下列表格的查询:
-
\(1\) \(i\) \(x\) : 修改 \(a_i := x\)
-
\(2\) \(k\) :在一个操作中,你可以选择任意一些元素 \(a_i\) 并赋值 \(a_i := (a_i + k) \pmod m\) 确定是否存在一些操作后(可能不操作)使 \(a\) 单调不降 \(^{\text{†}}\) 。
注意,查询 \(2\) 没有实际修改发生,查询 \(1\) 是真正修改 \(a_i\) 的
\(2 \le m \le 5 \times 10^5,1 \le k < m, 1 \le q \le 10^5\)
题解
可以发现,我们每次对一个 \(a_i\) 进行操作 2 的时候,其实相当于在 \(+\gcd(m, k)\) ,这个我不会严谨证明,但是确实比较显然,设 \(d = \gcd (m, k)\)
那么我们进行操作后的值其实也只跟 \(a_i \bmod d\) 的大小有关

那么我们其实可以发现,如果当前这一个 \(b_i = a_i \bmod d < b_{i - 1}\) 那么我们就需要将它加一个 \(d\) 来保证单调不降,但我们不能无休止的加 \(d\) ,它有个上限 \(m / d - 1\) 那么也就是说 我们最多加这么多次 \(d\)
我们还需要处理一些问题,对于每个询问 \(d\) 是不一样的,所以我们将询问离线下来,对每个 \(d\) 都询问一遍,然后找到 \(\gcd (m, k) = d\) 的询问 2 赋值即可,对于 \(m\) 预处理 \(d\) 即可
预处理的时间复杂度为 \(O(M\log M)\) ,总时间复杂度 为 \(O(d(M)q\log M)\) 大概 2e8,其实有点勉强了,不过 \(CF\) 不卡
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>using namespace std;namespace michaele {const int N = 2e5 + 10, M = 5e5 + 10;int q[N >> 1][3], ans[N >> 1];int a[N], b[N];vector <int> divs[M];void get_d () {for (int i = 1; i < M - 5; i++) {for (int j = i; j < M - 5; j += i) {divs[j].push_back (i);}}}//二进制 gcd 减小常数int gcd (int a, int b) {int az = __builtin_ctz (a);int bz = __builtin_ctz (b);int z = min (az, bz), diff;b >>= bz;while (a) {a >>= az;diff = a - b;if (!diff) break;az = __builtin_ctz (diff);b = a < b ? a : b;a = diff < 0 ? -diff : diff;}return b << z;}void solve () {int n, m, qn;cin >> n >> m >> qn;for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);for (int i = 1; i <= qn; i++) {scanf ("%d", &q[i][0]);if (q[i][0] == 1) {scanf ("%d%d", &q[i][1], &q[i][2]);} else {scanf ("%d", &q[i][1]);}}memset (ans, -1, sizeof ans);for (auto d : divs[m]) {int sum = 0;for (int i = 1; i <= n; i++) b[i] = a[i] % d;for (int i = 1; i < n; i++) {if (b[i] > b[i + 1]) sum++;}for (int i = 1; i <= qn; i++) {if (q[i][0] == 1) {int pos = q[i][1], x = q[i][2];if (pos - 1 >= 1 && b[pos] < b[pos - 1]) sum--;if (pos + 1 <= n && b[pos] > b[pos + 1]) sum--;b[pos] = x % d;if (pos - 1 >= 1 && b[pos] < b[pos - 1]) sum++;if (pos + 1 <= n && b[pos] > b[pos + 1]) sum++;} else {if (d == gcd (m, q[i][1])) {ans[i] = (sum < m / d);}}}}for (int i = 1; i <= qn; i++) {if (ans[i] == -1) continue;printf (ans[i] ? "YES\n" : "NO\n");}}void main () {get_d();int T;cin >> T;while (T--) solve ();}
}int main () {michaele :: main ();return 0;
}