首页 > 代码库 > HDU 1104Remainder

HDU 1104Remainder

 1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 #define MAXN 1000010 7 int c[MAXN]; 8 int fa[MAXN]; 9 int vis[MAXN];10 int s[MAXN];11 char op[5] = "+-*%";12 13 int mod(int a, int b) {14     return ( a % b + b) % b;15 }16 17 int main() {18     int des, n, k, m, next, now, mo, cnt;19     while (scanf("%d%d%d", &n, &k, &m) != EOF && k) {20         mo = m*k;21         queue <int> q;22         des = mod(n + 1, k);23         n = mod(n, mo);24         memset(vis, 0, sizeof (vis));25         q.push(n);26         vis[n] = 1;27         fa[n] = -1;28         c[n] = -1;29         while (!q.empty()) {30             now = q.front();31             q.pop();32             for (int i = 0; i < 4; ++i) {33                 if (i == 0)next = (now + m) % mo;34                 else if (i == 1)next = mod(now - m, mo);35                 else if (i == 2)next = now * m % mo;36                 else next = now % m;37                 if (!vis[next]) {38                     vis[next] = 1;39                     fa[next] = now;40                     c[next] = i;41                     if (next % k == des)42                         goto L;43                     q.push(next);44                 }45             }46         }47         printf("0\n");48         continue;49 L:50         cnt = 0;51         while (fa[next] >= 0) {52             s[cnt++] = c[next];53             next = fa[next];54         }55         printf("%d\n", cnt);56         while (cnt)57             printf("%c", op[s[--cnt]]);58         printf("\n");59 60     }61     return 0;62 }
代码搬运工

学会如何输出路径。

还有数论的知识。

HDU 1104Remainder