题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1104

题解：

又是一道数论宽搜题，因为栽到BFS的一个逻辑坑里，所以发一篇加深印象。

注意题目中的%是指mod，开始给了你n, k, m。每次由+m, -m, *m, mod m得到新的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记录路径。

因为题目没有一开始就等于结果的数据，所以我的程序中不是直接Q.push(s)开始，而是PUSH所有s的下一个节点，避免PRINT输出的时候陷入死循环。 

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1104.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

queue<int> Q;
int pre[1000000], cur[1000000], cnt[1000000];

void PRINT(int x) {
    if (pre[x] != -1) PRINT(pre[x]);
    switch (cur[x]) {
        case 1:
            printf("+");
            break;
        case 2:
            printf("-");
            break;
        case 3:
            printf("*");
            break;
        case 4:
            printf("%%");
            break;
    }
    return;
}

int mode(int t, int i, int m, int MOD) {
    switch (i) {
        case 1:
            return ((t + m) % MOD + MOD) % MOD;
        case 2:
            return ((t - m) % MOD + MOD) % MOD;
        case 3:
            return ((t * m) % MOD + MOD) % MOD;
        case 4:
            return (t % m + m) % m % MOD;
    }
    return 0;
}

void bfs(int s, int k, int m, int MOD) {
    int goal = ((s + 1) % k + k) % k;
    s = (s % MOD + MOD) % MOD;
    while (!Q.empty()) Q.pop();
    memset(pre, -1, sizeof(pre));
    memset(cur, 0, sizeof(cur));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= 4; ++i) {
        int v = mode(s, i, m, MOD);
        if (cur[v] == 0) {
            Q.push(v);
            pre[v] = -1, cnt[v] = 1, cur[v] = i;
        }
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if ((u % k + k) % k == goal) {
            printf("%d\n", cnt[u]);
            if (cnt[u]) {
                PRINT(u);
                printf("\n");
                return;
            }
        }
        for (int i = 1; i <= 4; ++i) {
            int v = mode(u, i, m, MOD);
            if (cur[v] == 0) {
                Q.push(v);
                pre[v] = u, cnt[v] = cnt[u] + 1, cur[v] = i;
            }
        }
    }
    printf("0\n");
    return;
}

int main() {
    int n, k, m;
    while (scanf("%d%d%d", &n, &k, &m), n || k || m) {
        bfs(n, k, m, k*m);
    }
    return 0;
}
转载保留版权：http://haipz.com/blog/i/5557 - 海胖博客