🧠 题解思路

✅ 本质问题

我们需要在操作若干步后使：

( 𝑁 init + 1 )   m o d   𝐾

𝑁 current   m o d   𝐾 (N init ​ +1)modK=N current ​ modK

设初始为 $n_0$，则目标是：

( 𝑛 0 + 1 )   m o d   𝐾

𝑛   m o d   𝐾 (n 0 ​ +1)modK=nmodK 这是一个最短路径搜索问题，目标是从状态 $n_0$ 出发，使用操作 + - * %，使得当前 $n$ 满足上述等式。

✅ 状态空间与转移

状态：当前 $N$ 的值（范围大约 $[-32768, 32767]$，不过我们只关注 $N \bmod K$ 的值，共 $K$ 个可能性）；

BFS搜索：使用 BFS 找到最短路径；

字典序优先：每个状态可以扩展为 4 个子状态，按操作顺序 + - * % 优先。

✅ 运算处理要点 加法：$n + M$

减法：$n - M$

乘法：$n \times M$

取模：$(n \bmod M + M) \bmod M$（保证非负）

✅ BFS搜索剪枝

用 visited 数组记录是否访问过某个 $N \bmod K$ 的状态；

每次记录路径字符串，并优先扩展字典序小的操作。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
long long n,m,k;
int vis[1000005];
struct Node
{
	string s;
	int step;
	long long num;
};
int bfs()
{
	Node a,next;
	a.step=0;
	a.num=n;
	a.s="";
	queue<Node>que;
	que.push(a);
	memset(vis,0,sizeof(vis));
	vis[(n%(m*k)+(m*k))%(m*k)]=1;
	while(!que.empty())
	{
		Node now=que.front();
		que.pop();
		if((now.num%k+k)%k==((n+1)%k+k)%k)
		{
			printf("%d\n",now.step);
			cout<<now.s<<endl;
			return 1;
		}
		next=now;
		next.step=now.step+1;
		next.num=(next.num+m)%(m*k);
		next.num=(next.num+(m*k))%(m*k);
		next.s+="+";
		if(!vis[next.num])
		{
			vis[next.num]=1;
			que.push(next);
		}
		
		next=now;
		next.step=now.step+1;
		next.num=(next.num-m)%(m*k);
		next.num=(next.num+(m*k))%(m*k);
		next.s+="-";
		if(!vis[next.num])
		{
			vis[next.num]=1;
			que.push(next);
		}
		
		next=now;
		next.step=now.step+1;
		next.num=(next.num*m)%(m*k);
		next.num=(next.num+(m*k))%(m*k);
		next.s+="*";
		if(!vis[next.num])
		{
			vis[next.num]=1;
			que.push(next);
		}
		
		next=now;
		next.step=now.step+1;
		next.num=(next.num%m+m)%m%(m*k);
		next.num=(next.num+(m*k))%(m*k);
		next.s+="%";
		if(!vis[next.num])
		{
			vis[next.num]=1;
			que.push(next);
		}
	}
	return -1;
}
int main()
{
	while(~scanf("%lld %lld %lld",&n,&k,&m)&&(n||m||k))
	{
		if(bfs()==-1) printf("0\n");
	}
	return 0;
}