题目链接（洛谷）
题目大意
给定两个数 \(u\) ， \(v\) 。有三种操作：
- \(u=u+1(mod\) \(p)\) 。
- \(u=u+p?1(mod\) \(p)\) 。
- \(u=u^{p?2}(mod\) \(p)\) 。
求最小能把 \(u\) 变为 \(v\) 的操作步数。
思路
BFS
状态太多导致队列装不下。
迭代加深
\(TLE\) ，浪费了太多时间在每一层上，没有记忆化且状态很多。
IDA*
不行，无法得出乐观估价函数。
双向BFS
这样会将步数很为两半，状态相较于普通的 \(BFS\) 会少很多。
先来看操作一和操作二，他们的关系是可以互逆的。一个对于原数 \(+1\) ，另一个对于原数 \(-1\) 。
操作三和操作三是互逆的，由费马小定理可知：若 \(p\) 为质数，则 \(a^{p-1}≡1(mod\) \(p)\)。
可得出：\((u^{p-2})^{p-2}≡u^{(p-2)(p-2)}≡u^{(p-1)(p-3)+1}≡(u^{p-1})^{p-3}u≡u(mod\) \(p)\)
那么就分别由开始状态与结束状态来向中间推进。
Code
#include