Number Clicker
题面翻译
小 y 在玩数学游戏，他有三种变化方式：
- 将该数 \(+1\)；
- 将该数 \(-1\)
- 将该数变成他的逆元（即 \(p-2\) 次幂），当然，我们所有操作都是在 \(\bmod\ p\) 意义下的
现在小 h 知道了变换前的数 \(u\) 和变换后的数 \(v\)，给定模数 \(p\) 保证是质数，他想知道怎么在 \(200\) 次操作之内得到 \(v\)。
\(p\le 10^9+9\)
Solution
尝试去找了一下三种操作之间有什么规律，然后发现确实没什么规律……
考虑构造一种操作，使它与题目要求的变化方式等价。由于存在逆元，所以我们将这个数表示成为 \(\dfrac a b\)。那么操作 \(1\) 对应 \(\dfrac {a+b}{b}\)，操作 \(2\) 对应 \(\dfrac {a-b}{b}\)，操作 \(3\) 对应 \(\dfrac b a\)。发现这个操作很像辗转相除法，所以考虑使用更相减损法来做这道题。
因为操作 \(1\) 和操作 \(2\) 是可逆的，并且操作 \(3\) 和操作 \(3\) 也是可逆的，所以可以考虑将变换前的数 \(u\) 和变换后的数 \(v\) 都变换成为一个数字后然后将一个操作序列反过来。不妨将这个数字设成 \(0\)。那么就是运用更相减损法将 \(u\) 和 \(v\) 分别变成 \(0\)。
初始的 \(a,b\) 并不好确认，所以可以直接随机 \(a\) 的取值，然后计算 \(b\)。如果直接使用更相减损法可能会直接超时，所以可以先使用辗转相除法计算步数，如果总步数 \(\le 200\) 就使用更相减损法构造答案。
复杂度 \(\mathcal O(\text{松松松})\)。
Code
// Cirno is not baka!
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define All(x) x.begin(), x.end()
#define pii pair<int, int>
#define fi first
#define se second
#define i64 long long
#define mkp make_pair
// #define int long long
#define epb emplace_back
using namespace std;
const int _N = 1e6 + 5, inf = 1e9;
template<typename T> void Max(T &x, T y) {x = max(x, y);}
template<typename T> void Min(T &x, T y) {x = min(x, y);}
#ifdef CIRNO
template<typename T> void Debug(T x) {cerr << x << '\n';}
template<typename T, typename ...Args> void Debug(T x, Args ...args) {cerr << x << ' '; Debug(args...);}
template<typename T> void Debug(vector<T> v) {for (T x: v) cerr << x << ' '; cerr << '\n';}
#else
#define Debug(...)
#endif
namespace BakaCirno {
mt19937 rnd(9);
#define Rand(l, r) uniform_int_distribution<>(l, r)(rnd)
int A, B, mod;
int Calc(int a, int b) {
if (b == 0) return 0;
return Calc(b, a % b) + a / b + 1;
}
vector<int> GetPath(int a, int b) {
vector<int> res;
while (b) {
if (a < b) res.epb(3), swap(a, b);
else res.epb(2), a -= b;
}
return res;
}
void _() {
cin >> A >> B >> mod;
while (true) {
int v1 = Rand(1, mod - 1), v2 = Rand(1, mod - 1);
if (Calc(1ll * v1 * A % mod, v1) + Calc(1ll * v2 * B % mod, v2) <= 200) {
vector<int> r1 = GetPath(1ll * v1 * A % mod, v1),
r2 = GetPath(1ll * v2 * B % mod, v2);
reverse(All(r2));
cout << r1.size() + r2.size() << '\n';
for (int x: r1) cout << x << ' ';
for (int x: r2) cout << (x < 3 ? 3 - x : 3) << ' ';
cout << '\n';
break;
}
}
}
}
void File(const string file) {
freopen((file + ".in").c_str(), "r", stdin);
freopen((file + ".out").c_str(), "w", stdout);
}
signed main() {
// File("");
cin.tie(0)->sync_with_stdio(0); int T = 1;
// cin >> T;
while (T--) BakaCirno::_();
}