学步园

2 2 2
-1 12 10
0 0 0

0
2
*+

看了他人的才AC，自己写的会超内存！！下面 的话是从他人的博客里面复制过来的，看起来还不错，就是有一点不明，为什么要余K*M（或是它们的公陪数）？

题意：（注意题目中的%是指mod）开始给了你n, k, m。。。。每次由+m, -m, *m, modm得到新的N，继续对N这样的操作,直到(n+1) mod k== N mod k时结束。。。并且打印路径

%与mod的区别：%出来的数有正有负，符号取决于左操作数。。。而mod只能是正（因为a = b * q + r (q > 0 and 0 <= r < q), then we have a mod q = r    中r要大于等于0小于q）。。。。。

所以要用%来计算mod的话就要用这样的公式：a mod b = (a % b + b) % b括号里的目的是把左操作数转成正数

 由于新的N可以很大，所以我们每一步都要取%，而且最后要mod k，正常来说每步都%k就行了，但是由于其中的一个操作是N%m,所以我们每一步就不能%k了（%k%m混用会导致%出来的答案错误），而要%(k *m)(其实%(k,m的公倍数都行))

然后，vis[这里放的要是遍历的点mod k (想清楚标记的目的是避免结果重复)]

而那四个操作避免过大则取余就可以了，而不需要取mod。记录路径，直接用string来累加路径就行了。。。

#include<iostream>
#include<queue>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef struct nn
{
    string way;
    int step,n;
}node;
int N,K,M,vist[1000000];
void BFS()
{
    queue<node>Q;
    node q,p;
    
    memset(vist,0,sizeof(vist));
    int i,km=K*M,mod=((N+1)%K+K)%K;//（N+1）%K余数要为正，为负时变正
    vist[(N%K+K)%K]=1; //记录余数有没有访问过
    for(i=0;i<4;i++)//一定要按照顺序更新n，因为在题目给定时，要求路径最小
    {
        q.way="";
        if(i==0)
        { q.n=(N+M)%km;q.way+='+';q.step=1;}
        if(i==1)
        { q.n=(N-M)%km;q.way+='-';q.step=1;}
        if(i==2)
        { q.n=(N*M)%km;q.way+='*';q.step=1;}
         if(i==3)
        { q.n=((N%M+M)%M)%km;q.way+='%';q.step=1;}

        if(vist[(q.n%K+K)%K]==0)
            Q.push(q);
        vist[(q.n%K+K)%K]=1;
    }
    while(!Q.empty())
    {
        q=Q.front();Q.pop();
        if((q.n%K+K)%K==mod)//找到
        {
            printf("%d\n",q.step);
                for(i=0;i<q.step;i++)
                printf("%c",q.way[i]);
                printf("\n");
            return ;
        }
        for(i=0;i<4;i++)
        {
            p.way=q.way;
            if(i==0)
            {
                p.n=(q.n+M)%km;//最km的余是因为如果不最余，那么n的值会很大
                p.way+='+';p.step=1+q.step;
            }
            if(i==1)
            {
                p.n=(q.n-M)%km;p.way+='-';p.step=1+q.step;
            }
            if(i==2)
            {
                p.n=(q.n*M)%km;p.way+='*';p.step=1+q.step;
            }
             if(i==3)
            {
                p.n=((q.n%M+M)%M)%km;p.way+='%';p.step=1+q.step;
            }
            if(vist[(p.n%K+K)%K]==0)//当不存在时可以放入，存在时如果放入那下次取出会重复和余数相同的步聚
                Q.push(p);
            vist[(p.n%K+K)%K]=1;
        }
    }
    printf("0\n");
}
int main()
{
    int i;
    while(scanf("%d%d%d",&N,&K,&M)>0&&(N||M||K))
    {
        BFS();
    }
}