题目分析
首先,我们必须明白,操作都是互逆的,\(1,2\)之间是可以互相转化的,这是不需证明的,对于操作\(3\),实际上,是求当前数的逆元,我们知道,逆元就是求当前数在模另一个数下的倒数,那么,逆元的逆元就是他本身也就是倒数的倒数
于是,所有的操作是可以转化的,对于搜索,其实就有用双向\(bfs\)的依据
采用此算法,需要注意,反向的操作需要转化为现在的正向操作
其实,一共也不会运算超过五秒的时间
#include <bits/stdc++.h>
using namespace std;
long long Pow(long long a, long long b, long long mod) {
long long base = a;
long long ans = 1;
while (b) {
if (b & 1) {
ans *= base;
ans %= mod;
}
base *= base;
base %= mod;
b >>= 1;
}
return ans;
}
long long u, v, p;
struct node {
long long sta;
int op;
vector<int> opera;
};
map<long long, int> vis[5];
vector<int> last1, last2;
map<long long, vector<int> > step[5];
void Bfs_Both() {
queue<node> q;
node A;
A.sta = u;
A.op = 0;
q.push(A);
vis[0][A.sta] = 1;
node B;
B.sta = v;
B.op = 1;
vis[1][B.sta] = 1;
q.push(B);
while (q.size()) {
node temp = q.front();
q.pop();
if (vis[(temp.op == 1) ? 0 : 1][temp.sta]) {
last1 = step[0][temp.sta];
last2 = step[1][temp.sta];
return;
}
node ply;
ply = temp;
ply.sta = (temp.sta + 1) % p;
if (!vis[ply.op][ply.sta]) {
vis[ply.op][ply.sta] = 1;
ply.opera.push_back(1);
step[ply.op][ply.sta] = ply.opera;
q.push(ply);
ply.opera.pop_back();
}
ply.sta = (temp.sta - 1 + p) % p;
if (!vis[ply.op][ply.sta]) {
vis[ply.op][ply.sta] = 1;
ply.opera.push_back(2);
step[ply.op][ply.sta] = ply.opera;
q.push(ply);
ply.opera.pop_back();
}
ply.sta = Pow(temp.sta, p - 2, p);
if (!vis[ply.op][ply.sta]) {
vis[ply.op][ply.sta] = 1;
ply.opera.push_back(3);
step[ply.op][ply.sta] = ply.opera;
q.push(ply);
ply.opera.pop_back();
}
}
}
int main() {
scanf("%lld %lld %lld", &u, &v, &p);
Bfs_Both();
printf("%d\n", last1.size() + last2.size());
for (int i = 0; i < last1.size(); i++) {
printf("%d ", last1[i]);
}
for (int i = last2.size()-1; i >=0 ; i--) {
if(last2[i]==1)
{
printf("2 ");
}
else if(last2[i]==2)
{
printf("1 ");
}
else
{
printf("%d ", last2[i]);
}
}
}