Number Clicker(双向BFS)

描述

传送门:Codeforces Round #492 (Div. 1) [Thanks, uDebug!] - Problem E

Allen is playing Number Clicker on his phone.

He starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.

  1. Turn $u \to u+1 \pmod{p}$
  2. Turn $u \to u+p-1 \pmod{p}$
  3. Turn $u \to u^{p-2} \pmod{p}$

Allen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!

Input

The first line of the input contains 3 positive integers: $u, v, p$($0 \le u, v \le p-1$,$3 \le p \le 10^9 + 9$). $p$ is guaranteed to be prime.

Output

On the first line, print a single integer $\ell$, the number of button presses. On the second line, print integers $c_1, \dots, c_\ell$, the button presses. For $1 \le i \le \ell$,$1 \le c_i \le 3$.

We can show that the answer always exists.

Examples

Input Output
1
1 3 5
1
2
2
1 1
1
3 2 5
1
2
1
3

Note

In the first example the integer on the screen changes as $1 \to 2 \to 3$.
In the second example the integer on the screen changes as $3 \to 2$.

思路

  • 大佬的博客中还是能学到一点东西的。
  • 由于$p$是质数,操作3就相当于是取逆元,所以有

$$x ^ {-1} \equiv x ^ {p - 2} \pmod {p} \\
x \equiv (x ^ {-1}) ^ {p - 2} \pmod {p}$$

  • 然后直接双向BFS即可。
  • 从大佬那里学了一手双向BFS的写法。

代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

#pragma optimize("-O3")

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

ll Pow(ll a, ll n, ll p)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= p)
if (n & 1) (t *= a) %= p;
return t;
}

queue<ll> q[2];
map<ll, pair<ll, int>> pre[2];
map<ll, int> vis[2];

inline void add(const ll& t, const ll& a, const int& d, const int& tag)
{
if (vis[d][a]) return;
q[d].push(a);
vis[d][a] = 1;
pre[d][a] = {t, tag};
}

VI gao(const ll& u, const ll& v, const ll& t)
{
VI ans;
for (ll x = t; x != u; x = pre[0][x].first) ans.push_back(pre[0][x].second);
reverse(ans.begin(), ans.end());
for (ll x = t; x != v; x = pre[1][x].first) ans.push_back(pre[1][x].second);
return ans;
}

VI bfs(const ll& u, const ll& v, const ll& p)
{
q[0].push(u);
q[1].push(v);
vis[0][u] = 1;
vis[1][v] = 1;
pre[0][u] = {u, 0};
pre[1][v] = {v, 0};
while (!q[0].empty() || !q[1].empty())
{
int n = q[0].size();
while (n--)
{
ll t = q[0].front();
q[0].pop();
if (vis[1].find(t) != vis[1].end()) return gao(u, v, t);
add(t, (t + 1) % p, 0, 1);
add(t, (t - 1 + p) % p, 0, 2);
add(t, Pow(t, p - 2, p), 0, 3);
}
int m = q[1].size();
while (m--)
{
ll t = q[1].front();
q[1].pop();
if (vis[0].find(t) != vis[0].end()) return gao(u, v, t);
add(t, (t + 1) % p, 1, 2);
add(t, (t - 1 + p) % p, 1, 1);
add(t, Pow(t, p - 2, p), 1, 3);
}
}
assert(false);
}

void go()
{
ll u, v, p;
cin >> u >> v >> p;
VI ans = bfs(u, v, p);
cout << ans.size() << endl;
for (auto& t : ans) cout << t << " ";
}
捐助作者
0%