LX同学想要游遍整个中国甚至全世界！所以这个国庆假期她计划去长沙玩。但是在她做旅行前的准备的时候，她收到了老师的作业，并且要求在国庆假期结束之前上交！LX同学非常的生气，告诉了你这个消息。你也觉得实在是太过分了，但是没有办法，只好帮助LX同学完成她的作业。
老师给了LX同学两个整数，分别是 x 和 y 。每次LX同学可以从中选择一个数 num ，把这个数变成 (num+2) mod p 或 (num∗2) mod p 或 (num∗num) mod p ，请问，最少需要多少次操作，能使这两个整数相等。 输入格式:
一行三个正整数 x,y,p(3≤p≤106,1≤x,y<p) ,保证p 是一个奇数。 输出格式:
一行一个整数表示最少操作次数。 样例1 输入样例
3 4 5
输出样例
1
样例2 输入样例
2 3 5
输出样例
2
提示
样例一解释：3∗3≡4(mod5) 。
样例二解释：3∗2≡1(mod5) ，1∗2≡2(mod5) 。
观察到数据比较大1e6
考虑两个数组X[]和Y[]X[i]存储x到i的最短路，Y[i]存储y到i的最短路则答案一定是两条路相加的最小值，即min(X[i]+Y[i])最短路直接bfs即可，注意去重剪枝，考虑一下dijkstra+堆优化是否可行复杂度理论上是O(N)的，因为从x开始X[1,1e6]每个数字最多被标记一次最短路 y也一样
#define debug #ifdef debug #include <time.h> #include "win_majiao.h" #endif #include <iostream> #include <algorithm> #include <vector> #include <stdlib.h> #include <string.h> #include <map> #include <set> #include <stack> #include <queue> #include <math.h> #define MAXN ((int)1e6+7) #define ll long long int #define INF (0x7f7f7f7f) #define fori(lef, rig) for(int i=lef; i<=rig; i++) #define forj(lef, rig) for(int j=lef; j<=rig; j++) #define fork(lef, rig) for(int k=lef; k<=rig; k++) #define QAQ (0) using namespace std; typedef vector<vector<int> > VVI; #define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0) void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... A> void err(T a, A... x) { cout << a << ' '; err(x...); } namespace FastIO{ char print_f[105]; void read() {} void print() { putchar('\n'); } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { x = 0; char ch = getchar(); ll f = 1; while (!isdigit(ch)) { if (ch == '-') f *= -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; read(oth...); } template <typename T, typename... T2> inline void print(T x, T2... oth) { ll p3=-1; if(x<0) putchar('-'), x=-x; do{ print_f[++p3] = x%10 + 48; } while(x/=10); while(p3>=0) putchar(print_f[p3--]); putchar(' '); print(oth...); } } // namespace FastIO using FastIO::print; using FastIO::read; int n, m, Q, K, x, y, p; int X[MAXN], Y[MAXN]; struct Node { int x, step; bool operator < (const Node& no) const { return step < no.step; } } ; queue<Node> q1, q2; void bfs(int start, int* a, queue<Node>& q) { q.push({start, 0}); ll cnt = 0; while(!q.empty()) { auto& now = q.front(); ll v = now.x, step = now.step; a[v] = step; cnt ++; ll calc = (v + 2) % p; if(a[calc] == INF) { //A q.push({calc, step+1}); a[calc] = step + 1; } calc = (v*2) % p; if(a[calc] == INF) { //B q.push({calc, step+1}); a[calc] = step + 1; } calc = ((v%p)*(v%p)) % p; //注意这里乘起来可能会爆int 这个地方RE了好久 if(a[calc] == INF) { //C q.push({calc, step+1}); a[calc] = step + 1; } q.pop(); } // printf("cnt : %lld\n", cnt); } #if 0 void bfs(int start, int* a) { //a[i]表示x变成i的最少步数 for(int i=1; i<=n; i++) { ll now = (i+2) % p; a[now] = min(a[now], a[i]+1); /** * x y * 1 2 3 4 5 6 7 8 9 10 * 0 0 1 1 2 2 3 2 2 3 * */ } } #endif signed main() { #ifdef debug freopen("test.txt", "r", stdin); clock_t stime = clock(); #endif memset(X, INF, sizeof(X)); memset(Y, INF, sizeof(Y)); read(x, y, p); X[x] = Y[y] = 0; bfs(x, X, q1); bfs(y, Y, q2); ll ans = INF; // forarr(X, 1, p); // forarr(Y, 1, p); //用X[i]存储x到i的最小步数(bfs出来) //用Y[i]存储y到i的最小步数(bfs出来) //则答案一定是min(X[i]+Y[i]) 两段路加起来最短即可 for(int i=1; i<=p; i++) { //O(n)的for if(X[i] == INF || Y[i] == INF) continue ; ans = min(ans, ((ll)X[i] + Y[i])); } printf("%lld\n", ans); #ifdef debug clock_t etime = clock(); printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC); #endif return 0; }