Codeforces 801E

发表于 |

题目

给整数M和一个长度为N的数列${a_i}$，其中$0\leq a_i\leq M−1$。

构造一个最长的数列${b_i}$，满足如下性质：

  1. $0\leq b_i\leq M−1$
  2. 前缀积模M的值各不相同
  3. 前缀积模M的值不在数列${a_i}$中出现

数据范围

$0\leq N\leq M\leq 200000$

做法

此题对数列${b_i}$没什么要求，对其前缀积有要求，考虑从前缀积下手，只要构造出了前缀积，原数列也能求出来。设前缀积为$p_1,p_2,\cdots,p_k$，则有$p_i−1\times b_i \equiv p_i\mod M$，而这个式子有解等价于$gcd(p_i−1,M)|p_i$。注意到，$gcd(p_i,M)=gcd(p_j,M)$时，$p_i$和$p_j$可以相邻。所以，按照$gcd(p_i,M)$的值将$p_i$分类。以$gcd(p_i,M)$的值作为顶点，以整除关系来连有向边，建一个DAG，跑最长路即可。对前缀积0特判一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_M = 2e5 + 5;
int N, M;
bool ban[MAX_M];
vector<int> Gcd[MAX_M];
int d[MAX_M], nxt[MAX_M];
ll extgcd(ll a, ll b, ll &x, ll &y)
{
  ll d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1; y = 0;
  }
  return d;
}
int GetNum(int a, int b, int mod)
{
  ll x, y;
  ll d = extgcd(a, mod, x, y);
  x = (x % mod + mod) % mod;
  int x0 = (x * (b / d) % mod + mod) % mod;
  return x0;
}
int MaxDist(int v)
{
  if (d[v] != -1) return d[v];
  if (Gcd[v].size() == 0) return d[v] = 0;
  int ans = Gcd[v].size();
  for (int i = 2 * v; i < M; i += v) {
    int tmp = MaxDist(i);
    if (ans < tmp + (int)Gcd[v].size()) {
      ans = (int)Gcd[v].size() + tmp;
      nxt[v] = i;
    }
  }
  return d[v] = ans;
}
int main()
{
  cin >> N >> M;
  for (int i = 0; i < N; ++i) {
    int tmp; scanf("%d", &tmp);
    ban[tmp] = 1;
  }
  for (int i = 1; i < M; ++i) {
    if (!ban[i]) {
      Gcd[__gcd(i, M)].push_back(i);
    }
  }
  memset(d, -1, sizeof d);
  memset(nxt, -1, sizeof nxt);
  MaxDist(1);
  int max_dist = 0, start = 0;
  for (int i = 1; i < M; ++i) {
    int tmp_dist = MaxDist(i);
    if (max_dist < tmp_dist) {
      max_dist = tmp_dist;
      start = i;
    }
  }
  printf("%d\n", max_dist + (!ban[0]));
  int pre_num = 1;
  while (nxt[start] != -1) {
    for (auto cur_num : Gcd[start]) {
      printf("%d ", GetNum(pre_num, cur_num, M));
      pre_num = cur_num;
    }
    start = nxt[start];
  }
  for (auto cur_num : Gcd[start]) {
    printf("%d ", GetNum(pre_num, cur_num, M));
    pre_num = cur_num;
  }
  if (!ban[0]) printf("0");
  return 0;
}

注意

extgcd中的乘法可能会爆int