挺难的，但没有 DP 好评（）
Div2 A
Description
假设一个人有 $n$ 点血，定义他的等级为 $$ \begin{cases}\text{A}&n\bmod4=1\\ \text{B}&n\bmod4=3\\ \text{C}&n\bmod4=2\\ \text{D}&n\bmod4=0 \end{cases}$$。并定义等级由 $\text{D}\sim\text{A}$ 依次更好。
现在给出一个人的血量 $x$，他可以回 $0\sim2$ 点血。问回几点血得到的等级最高。
Solution
分类讨论即可。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
int main()
{
int n;
cin >> n;
if (n % 4 == 1)
cout << 0 << " " << "A" << endl;
else if (n % 4 == 2)
cout << 1 << " " << "B" << endl;
else if (n % 4 == 3)
cout << 2 << " " << "A" << endl;
else
cout << 1 << " " << "A" << endl;
}
Div2 B
Description
Tokitsukaze 有 $3$ 块麻将，每个麻将上有一个 $2$ 位的字符串，由 $1\sim9$ 的一位数字和 m/s/p 组成，现在有两种出牌方式：
- 3个完全一样的麻将；
- 第2位相同，前面是连号的（比如1p，2p，3p就可以）。
但是 Tokitsukaze 不是个遵守规则的人，TA可以把任意一个麻将换成另一种麻将，可以换多次，也可以不换。问 Tokitsukaze 至少要换多少次才能一次出完 $3$ 个麻将？
Solution
模拟，但是可以想办法简化代码。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using std::cin;
using std::cout;
using std::endl;
std::string a, b, c;
std::string s[3];
int main()
{
cin >> a >> b >> c;
if (a == b && b == c) // 三个一样
{
cout << 0 << endl;
return 0;
}
s[0] = a, s[1] = b, s[2] = c;
std::sort(s, s + 3);
if (s[0][0] + 1 == s[1][0] && s[1][0] + 1 == s[2][0] && s[0][1] == s[1][1] && s[2][1] == s[1][1])
{
cout << 0 << endl; // 已经是顺子
return 0;
}
if (s[0] == s[1] || s[1] == s[2] || s[0] == s[2])
{
cout << 1 << endl; // 两个一样
return 0;
}
for (int i = 0; i < 2; i++)
for (int j = i + 1; j < 3; j++)
{
if ((s[i][0] + 1 == s[j][0] || s[j][0] + 1 == s[i][0] || s[i][0] + 2 == s[j][0] || s[j][0] + 2 == s[i][0]) && s[i][1] == s[j][1])
{
cout << 1 << endl; // 两个相邻或差一个
return 0;
}
}
cout << 2 << endl;
}
A
Description
最近，Tokitsukaze 发现了一个有趣的游戏。在游戏开始，有 $n$ 个数（$1\sim n$）。这 $n$ 个数每 $k$ 个被分为一组（最后一组可能不到 $k$ 个）。现在她想拿出 $m$个数 $p_1, p_2,\dots,p_m$（输入保证该序列为升序）。她会从 $1$ 到 $n$ 逐个看，如果发现了她想要的数，那么她会将这组数中所有她想要的都取走，算作一次操作。一次操作结束后，数列中的数会自动左移补上被拿出的数的位置，但数值不变。求经过多少次操作后，她能取到所有她想要的数？$1\leq n\leq10^{18},1\leq m\leq10^5$。
Solution
显然需要一个 $O(m)$ 的算法，我们对于每个数，算出来它在哪个块里，然后把在块里的数全跳过去就行。
假设当前数是 $p_i$，之前已经拿了 $del=i-1$ 个数，那么它所在的块就是 $\lceil\dfrac{p_i-del}{k}\rceil$。
Code
要注意 ceil 返回值是 double，会有精度问题，用返回值是 long double 的 ceill 就没有这个问题了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;
const int maxn = 1e5 + 10;
typedef long long ll;
ll n, m, k;
ll a[maxn];
int main()
{
cin >> n >> m >> k;
ll now = 1, ans = 0;
for (int i = 1; i <= m; i++)
cin >> a[i];
while (now <= m)
{
ll del = now - 1;
ll nowblock = ceill(1.0l * (a[now] - del) / k);
while ((ll)ceill(1.0l * (a[now] - del) / k) == nowblock)
now++;
ans++;
}
cout << ans << endl;
}
B
Description
A 和 B 在玩一个小游戏，轮流从 $n$ 堆石子里拿石子，一次拿一个。当拿之前所有石子都被拿完了或拿完一个石子之后有两堆石子剩余个数一样（包括都为空的石子），A 先手，问谁能赢。
Solution
手玩一下发现当两个人开始轮流取的时候，取什么都是一样的，而最终一定会变成每堆石子的数目分别为 $0\sim n-1$ 这种情况。
所以直接算一下每堆石子和最终状态差值，看看是奇数还是偶数就知道谁赢了。
需要提前看一下能不能进入轮流取的情况，即先手拿完第一下会不会输。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
using std::cin;
using std::cout;
using std::endl;
const int maxn = 1e5 + 10;
int n, a[maxn];
std::map<int, int> cnt;
bool check()
{
cnt.clear();
for (int i = 0; i < n; i++)
if (cnt.count(a[i]))
return false;
else
cnt[a[i]] = 1;
if (cnt[0] == n)
return false;
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i], cnt[a[i]]++;
int ok = 1;
if (cnt[0] >= 2) // 有不止一个 0，先手输
{
cout << "cslnb" << endl;
return 0;
}
int tot = 0;
for (int i = 0; i < n; i++)
{
if (cnt[a[i]] >= 3) // 同一个数出现超过两次，先手输
{
ok = 0;
break;
}
else if (cnt[a[i]] >= 2) // 同一个数出现两次，比它小 1 的数出现过，先手输
{
if (cnt[a[i] - 1] >= 1)
{
ok = 0;
break;
}
}
}
for (auto k : cnt)
{
if (k.second >= 2)
tot++;
}
if (tot >= 2) // 出现两次的数超过 1 个，先手输
{
ok = 0;
}
if (!ok)
{
cout << "cslnb" << endl;
return 0;
}
std::sort(a, a + n);
long long sum = 0;
for (int i = 0; i < n; i++)
{
sum += std::max(0, a[i] - i);
}
cout << (sum % 2 ? "sjfnb" : "cslnb") << endl;
}
C
Description
有一个长度为 $n$ 的01字符串，和一个整数 $k$。A、B。二人进行做博弈游戏，每个人必须选择连续的 $k$ 个字符，把这连续的 $k$ 个字符全变为 $0$ 或者 $1$。
如果某次操作之后整个字符串全为 $1$ 或者 $0$，那么这个人胜利，假设二人都绝顶聪明。给你初始局面，A先手，问 A、B 谁能赢，又或者平局。
Solution
发现一个事情：如果先手第一次操作后赢不了，那么以后永远都赢不了。因为后手可以把他的操作改回去。
而如果后手第一次操作后赢不了，那么必定平局——即把先手操作改回去来防御，如此循环。
判断先手能不能赢很简单，前缀和一下即可。
怎么判断后手能不能赢呢？
首先必须满足 $k\neq1\operatorname{and}2k\geq n$，前一个要求很好理解，后一个要求就是说如果先手赢不了，他直接修改两边就行，后手赢不了。
我们先枚举先手选的区间 $[l,r]$，如果 $a_{l-1}\neq a_{l}\operatorname{or} a_r\neq a_{r+1}$，那么就会平局（先手可以把这个区间全改成挨着它的那个颜色，这样后手就改不过来）。如果每一个区间先手都没法让他变平局，后手胜利。
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
const int maxn = 1e5 + 10;
int n, a[maxn], sum[maxn], k;
char ss[maxn];
inline int s(int l, int r) { return l > r ? 0 : sum[r] - sum[l - 1]; }
bool check1()
{
for (int i = 1; i + k - 1 <= n; i++)
{
int p = s(1, i - 1) + s(i + k, n); // 判断先手必胜
if (p == 0 || p + k == n)
return true;
}
return false;
}
bool check2()
{
if (k == 1 || k * 2 < n)
return false;
for (int i = 2; i <= n - k - 1; i++)
{
if (a[i] != a[i - 1] || a[i + k] != a[i + k + 1])
return false;
}
return a[1] != a[n];
}
int main()
{
cin >> n >> k >> (ss + 1);
for (int i = 1; i <= n; i++)
a[i] = ss[i] - '0', sum[i] = sum[i - 1] + a[i];
if (check1())
{
cout << "tokitsukaze" << endl;
return 0;
}
else if (check2())
{
cout << "quailty" << endl;
}
else
{
cout << "once again" << endl;
}
}
D
Description
平面上有 $n$ 个点，坐标为 $(x_i,y_i)$，有三条直线，两条平行 $y$ 轴，一条平行 $x$ 轴，他们会围起一些点。如图：
求对于这三条线所有的可能，有多少种非空点集会被这三条线围起来。
$n\leq2\times10^5,1\leq x_i,y_i\leq10^9$。
Solution
发现这个平行 $x$ 轴的直线可以作为突破点。
首先把所有点坐标离散化一下。
我们从上到下移动这条线 $y=a$，当它扫到一个点时，我们把所有 $y\geq a$ 的点的答案都算进去。这样就不会算重也不会漏。
考虑这条线上只有一个点的情况，那么新的点集数就是 $cnt(1,x)\times cnt(x,x_{max})$，其中 $cnt(l,r)$ 表示在 $x=l$ 到 $x=r$ 这段闭区间内每条总共有几个横坐标不同的点（注意新扫到的点也算在内），解释就是从左面的直线有 $cnt(1,x)$ 种可以取的地方，右面同理，然后乘法原理一下。
如果直线上有多个点呢？我们先把所有点都算进去，然后对于每个点的贡献就是 $cnt(nxt+1,x)\times cnt(x,x_{max})$，其中 $nxt$ 是这条直线上在当前点左面的点的横坐标。
怎么维护 $cnt$？发现我们需要单点加区间求和，那么树状数组就可以胜任了。
时间复杂度 $O(n\log n)$。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using std::cout;
using std::endl;
const int maxn = 2e5 + 10;
struct point
{
int x, y;
} a[maxn];
int XX[maxn], YY[maxn], n, totx, toty, cnt[maxn];
std::vector<int> p[maxn];
inline int lowbit(int x) { return x & -x; }
struct Tree
{
int t[maxn], n;
void modify(int x, int v)
{
for (; x <= n; x += lowbit(x))
t[x] += v;
}
int get(int x)
{
int res = 0;
for (; x; x -= lowbit(x))
res += t[x];
return res;
}
int query(int l, int r) { return get(r) - get(l - 1); }
} t;
void init()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &XX[i], &YY[i]), a[i].x = XX[i], a[i].y = YY[i];
std::sort(XX + 1, XX + 1 + n), std::sort(YY + 1, YY + 1 + n);
totx = std::unique(XX + 1, XX + 1 + n) - XX - 1, toty = std::unique(YY + 1, YY + 1 + n) - YY - 1;
for (int i = 1; i <= n; i++)
a[i].x = std::lower_bound(XX + 1, XX + 1 + totx, a[i].x) - XX, a[i].y = std::lower_bound(YY + 1, YY + 1 + toty, a[i].y) - YY;
for (int i = 1; i <= n; i++)
p[a[i].y].push_back(a[i].x);
for (int i = 1; i <= toty; i++)
std::sort(p[i].begin(), p[i].end());
t.n = n;
}
int main()
{
init();
long long ans = 0;
for (int y = toty; y >= 1; y--)
{
int nxt = 1;
for (int x : p[y])
if (cnt[x] == 0)
t.modify(x, 1), cnt[x]++;
for (int x : p[y])
ans += 1ll * t.query(nxt, x) * t.query(x, totx), nxt = x + 1;
}
cout << ans << endl;
}
E
Description
给定平面上$N$个关键点，现在你可以放置 $M$ 条直线，直线之间可以相交，需要满足所有关键点与原点之间的线段至少与你放置的一条直线相交（相交在端点也算相交）。如果有一个关键点就是原点，那么一定要满足有一条直线经过原点。
你需要求出在满足上述条件的情况下原点到所有放置的直线的距离的最小值的最大可能值是多少。
$n,x_i,y_i,m\leq10^5$。
Solution
显然可以二分答案 $ans$，可以发现我们选择的直线一定在原点为圆心，半径为 $ans$ 的圆的切线上（因为这样更优）。
发现一个点到原点的直线被一条选择的直线经过等价于这条被选择的直线与圆的切点在这个点到圆两条切线之间的圆弧上。
那么我们的问题就转化为圆上有若干个圆弧，要覆盖整个圆，求这 $m$ 个圆弧能不能达成目的。
这个问题如果在序列上做是很经典的题，就是区间覆盖，按照左端点排序即可。我们可以把一个圆弧用两个角度来表示就实现了转化。
但是现在是在一个环上，我们肯定把长度变为二倍然后变成序列题目。
直接找一个起点跑是 $O(n^2)$ 的，不行。
我们可以想办法预处理一些什么东西。
发现对于每条线段，我们如果选择它，那么选择的下一条线段是确定的。这个东西可以用类似双指针的算法预处理出来。
然后，如果每步的决策是固定的，我们显然可以倍增优化。
$f_{i,j}$ 表示第 $i$ 条线段选 $2^j$ 条线段之后下一个到了哪条线段。然后就行了。
时间复杂度 $O(n\log n\log d)$，$d$ 是到原点最近的点到原点的距离。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;
const int maxn = 1e5 + 10;
const double eps = 1e-10, pi = acos(-1.0), pi2 = pi * 2;
struct seg
{
double l, r;
bool operator<(const seg &b) const { return l < b.l; }
} s[maxn * 2];
struct point
{
double x, y, diss;
double dis() { return diss = sqrt(x * x + y * y); }
} p[maxn];
int n, m, n2;
int f[maxn * 2][25];
int end(int x, int d)
{
for (int i = 0; d; i++, d >>= 1)
if (d & 1)
x = f[x][i];
return x;
}
bool check(double x)
{
for (int i = 1; i <= n; i++)
{
double k = atan2(p[i].y, p[i].x), delta = acos(x / p[i].diss);
s[i] = {k - delta, k + delta};
if (s[i].l < 0)
s[i].l += pi2, s[i].r += pi2;
s[i + n] = {s[i].l + pi2, s[i].r + pi2};
}
std::sort(s + 1, s + 1 + 2 * n);
f[n2 + 1][0] = n2 + 1;
int r = n2, l = n2;
for (; l; l--)
{
while (s[r].l > s[l].r)
r--;
f[l][0] = r + 1;
}
for (int i = 1; i <= 19; i++)
for (int j = 1; j <= n2 + 1; j++)
f[j][i] = f[f[j][i - 1]][i - 1];
for (int i = 1; i <= n; i++)
if (end(i, m) >= i + n)
return true;
return false;
}
int main()
{
cin >> n >> m, n2 = n * 2;
double r = 1e18, l = 0.0;
for (int i = 1; i <= n; i++)
{
cin >> p[i].x >> p[i].y;
r = std::min(p[i].dis(), r);
}
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.10lf\n", l);
}
F
Description
给出三个整数 $n,m,p$，试求出 $n$ 个互不相同的整数使得它们中的每个整数 $x$ 均满足以下条件：
- $x \in [0,m-1]$
- $\gcd(m,x) = 1$
- $\nexists e,k \in \mathbb{N},p^e = km+x$
如果能够找到，输出可能的选择方案，否则输出 -1。
$1 \leq n \leq 5 \times 10^5 , 1 \leq p < m \leq 10^{18}$，保证 $m$ 是某个质数的正整数次幂。
Solution
完全不会，以下是从各路题解拼凑出来的东西。
明确一下题目要求，设 $S=\{x|x\in\mathbb Z,0\leq x<m,\gcd(m,x)=1\},T=\{p^e\bmod m|e\in N\}$，我们需要从集合 $S-T$ 中找出 $n$ 个数。
设 $m=q^k$。
要判断有解，我们显然需要判断 $S-T$ 的大小。显然 $|S|=\varphi(m)=q^k-q^{k-1}=m(1-\dfrac{1}{q})$。
当 $\gcd(q,m)>1$，$m$ 是 $q$ 的倍数，那么 $T=\{p^0\}=\{1\}$。（$0$ 不合法）此时 $|S-T|=\varphi(m)-1$，判是否有解然后暴力枚举一组解就行。
否则 $T\subseteq S$，我们需要求出来 $|T|$，集合 $T$ 肯定是循环的，其实就是求 $p$ 的阶 $\text{order(p)}$，这玩意是 $\varphi(m)$ 的约数，而约数个数是不多的，我们可以用 Pollard-Rou 分解质因数然后枚举因数检查就能知道 $p$ 的阶。那么如果 $\varphi(m)-\text{order}(p)<n$，无解。
下面是构造解的过程：
当 $m$ 存在原根 $g$ 时，设 $p\equiv g^u\pmod m$，那么一个数 $p^e=g^{ue}\equiv g^{ue\ \bmod\ \varphi(m)}\pmod m$ （由欧拉定理）在 $T$ 中当且仅当关于 $e$ 的方程 $ue\equiv v\pmod{\varphi(m)}$ 有解。这个有解的充要条件是 $\gcd(u,\varphi(m))\mid v$。又由于 $(g^{u})^{\text{order}(p)}\equiv1\pmod m$，可以得出 $u=\dfrac{\varphi(m)}{\text{order}(p)}$（欧拉定理）。
这样就得出了不合法的数的性质，我们从小到大暴力枚举指数，检查是否合法即可。
当 $m$ 不存在原根即 $m=2^k,k\geq3$，且 $p$ 是奇数（因为要互质）。
用以下做法：
- 当 $m\leq10^7$，暴力。
- 当 $p=4x+1$，$\forall e\in\mathbb N,p^e\equiv1\pmod4$，那么我们直接在模 $4$ 余 $3$ 的数里选即可，因为数据范围很大，总能找到。
- 当 $p=4x+3$，我们只能选模 $4$ 余 $1$ 的数，注意到在 $p^e$ 中，$1$ 和 $3$ 总是交替出现。那么把 $p$ 换成 $p^2$。还有一个事情是：在模 $2^k$（$k\geq3$）意义下，取一个伪原根 $g’=5$，任意一个模 $4$ 余 $1$ 的数都可以用 $g’$ 的若干次幂表示出。可以对 $k$ 用归纳法证明，我懒了。于是就用有原根的方法做即可。
顺便一提，怎么找原根呢？上定理！
原根判定定理：设 $m \geqslant 3, \gcd(a,m)=1$，则 $a$ 是模 $m$ 的原根的充要条件是，对于 $\varphi(m)$ 的每个素因数 $p$，都有 $a^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m$。
最小原根的数量级：若 $m$ 有原根，则其最小原根是不多于 $m^{0.25}$ 级别的。
我们只需要分解质因数，然后从小到大原根枚举检验即可。
Code
不好写，因为这题实在太难，参考了 CF 上别人的代码。
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
typedef __int128_t ll;
namespace IO
{
const int mxsiz = 1 << 20;
char inbuf[mxsiz], *p1, *p2;
char outbuf[mxsiz], *op = outbuf;
struct endio
{
endio(){};
~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
} useless_var;
inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
#define isdigit(x) (x >= '0' && x <= '9') // 防止忘记打 <cctype> 头文件
inline ll read()
{
ll x = 0;
int f = 1;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = gc())
x = x * 10 + ch - '0';
return x * f;
}
template <typename T>
inline void read(T &x)
{
x = 0;
int f = 1;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = gc())
x = x * 10 + ch - '0';
x *= f;
}
#undef isdigit
inline bool ischar(char x)
{
return x >= 'A' && x <= 'z';
}
inline char readchar()
{
char ch = gc();
while (!ischar(ch))
ch = gc();
return ch;
}
inline void push(char ch)
{
if (op - outbuf == mxsiz)
fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
*op++ = ch;
}
template <typename T>
inline void work_wt(T x)
{
if (x > 9)
work_wt(x / 10);
push(x % 10 + '0');
}
template <typename T>
inline void write(T x)
{
if (x < 0)
x = -x, push('-');
work_wt(x);
}
inline void writestr(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
push(s[i]);
}
inline void endln() { push('\n'); }
inline void space() { push(' '); }
template <typename T>
inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;
const ll inf = 1e18;
ll n, m, p;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(ll a, ll x, ll p)
{
ll res = 1;
for (; x; x >>= 1, a = a * a % p)
if (x & 1)
res = res * a % p;
return res;
}
bool MR(ll x)
{
if (x < 3 || x % 2 == 0)
return x == 2;
ll a = x - 1, b = 0;
while (a % 2 == 0)
a /= 2, b++;
for (ll times = 0, j; times < 10; times++)
{
ll c = rand() % (x - 2) + 2, v = qpow(c, a, x);
if (v == 1)
continue;
for (j = 0; j < b; j++)
{
if (v == x - 1)
break;
v = v * v % x;
}
if (j >= b)
return false;
}
return true;
}
ll myabs(ll x) { return x < 0 ? -x : x; }
ll PR(ll x)
{
ll c = rand() % (x - 1) + 1, val = 1, s = 0, t = 0;
for (ll lim = 1;; lim <<= 1, s = t, val = 1)
{
for (ll step = 1; step <= lim; step++)
{
t = (t * t + c) % x;
val = val * myabs(t - s) % x;
if (step % 127 == 0)
{
ll d = gcd(val, x);
if (d > 1)
return d;
}
}
ll d = gcd(val, x);
if (d > 1)
return d;
}
}
void out_ans(const std::vector<ll> &ans)
{
if (ans.size() < n)
writeln(-1);
else
{
for (int i = 0; i < n; i++)
write(ans[i]), space();
endln();
}
}
namespace BF
{
const int maxm = 1e7 + 10;
bool vis[maxm];
void solve()
{
ll now = p;
vis[1] = 1;
while (!vis[now])
{
vis[now] = 1;
now = now * p % m;
}
for (int i = 2; i <= m; i++)
if (m % i == 0)
{
for (int j = 1; i * j <= m; j++)
vis[i * j] = 1;
break;
}
std::vector<ll> ans;
for (int i = 1; i <= m; i++)
if (!vis[i])
ans.push_back(i);
out_ans(ans);
}
}
struct primes
{
ll val;
int times;
bool operator<(const primes &b) const { return val < b.val; }
};
std::vector<primes> all;
void PF(ll x, int times)
{
if (x == 1)
return;
if (MR(x))
{
all.push_back({x, times});
return;
}
ll g = x, t = 0;
while (g >= x)
g = PR(g);
while (x % g == 0)
x /= g, t++;
PF(g, times * t), PF(x, times);
}
void find_order(int pos, ll val, ll &ans)
{
if (pos == (int)all.size())
{
if (qpow(p, val, m) == 1)
ans = std::min(ans, val);
return;
}
for (int i = 0; i <= all[pos].times; i++)
find_order(pos + 1, val, ans), val = val * all[pos].val;
}
std::map<ll, int> mp;
int main()
{
n = read(), m = read(), p = read();
srand(time(0));
if (m <= 1e7)
{
BF::solve();
return 0;
}
std::vector<ll> ans;
PF(m, 1);
ll q = all[0].val;
if (p % q == 0)
{
for (ll i = 2; i <= m && ans.size() < n; i++)
if (i % q != 0)
ans.push_back(i);
out_ans(ans);
return 0;
}
all.clear();
ll phi = m - m / q;
PF(phi, 1);
for (auto k : all)
mp[k.val] += k.times;
all.clear();
for (auto k : mp)
all.push_back({k.first, k.second});
ll order = inf, g;
find_order(0, 1, order);
if (phi - order < n)
{
writeln(-1);
return 0;
}
if (q == 2)
{
if (p % 4 == 1)
for (ll i = 3; ans.size() < n; i += 4)
ans.push_back(i);
else
{
p = p * p % m;
g = 5;
for (ll i = 1, now = g; ans.size() < n; i++, now = now * g % m)
if (i % (phi / order) != 0)
ans.push_back(now);
}
}
else
{
for (ll i = 2;; i++)
{
bool flag = 1;
for (int j = 0; j < (int)all.size() && flag; j++)
flag &= qpow(i, phi / all[j].val, m) != 1;
if (flag)
{
g = i;
break;
}
}
for (ll i = 1, now = g; ans.size() < n; i++, now = now * g % m)
if (i % (phi / order) != 0)
ans.push_back(now);
}
out_ans(ans);
}