首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。