# POJ2426总结

## Remainder

### Description

Coco is a clever boy, who is good at mathematics. However, he is puzzled by a difficult mathematics problem. The problem is: Given three integers N, K and M, N may adds (‘+’) M, subtract (‘-‘) M, multiples (‘*’) M or modulus (‘%’) M (The definition of ‘%’ is given below), and the result will be restored in N. Continue the process above, can you make a situation that “[(the initial value of N) + 1] % K” is equal to “(the current value of N) % K”? If you can, find the minimum steps and what you should do in each step. Please help poor Coco to solve this problem.

You should know that if a = b * q + r (q > 0 and 0 <= r < q), then we have a % q = r.

### Input

There are multiple cases. Each case contains three integers N, K and M (-1000 <= N <= 1000, 1 < K <= 1000, 0 < M <= 1000) in a single line.

The input is terminated with three 0s. This test case is not to be processed.

### Output

For each case, if there is no solution, just print 0. Otherwise, on the first line of the output print the minimum number of steps to make “[(the initial value of N) + 1] % K” is equal to “(the final value of N) % K”. The second line print the operations to do in each step, which consist of ‘+’, ‘-‘, ‘*’ and ‘%’. If there are more than one solution, print the minimum one. (Here we define ‘+’ < ‘-‘ < ‘*’ < ‘%’. And if A = a1a2…ak and B = b1b2…bk are both solutions, we say A < B, if and only if there exists a P such that for i = 1, …, P-1, ai = bi, and for i = P, ai < bi)

```2 2 2
-1 12 10
0 0 0
```

```0
2
*+```

### 我的代码

``````#include<stdio.h>
#include<stack>
#include<string.h>
#include<vector>
using namespace std;

struct node{
int now,pre,step;
char ope;
node(){
}
node(int now,int pre,int step,char ope):now(now),pre(pre),step(step),ope(ope){
}
};

const char opes[6]={'0','+','-','*','%'};
int flag[1001];
vector<char> trail;
stack<char> s;
vector<node> v;
node temp;

int solve(int now,int o){
switch (o){
case '+':
return ((now+m)%k+k)%k;
case '-':
return ((now-m)%k+k)%k;
case '*':
return ((now*m)%k+k)%k;
default :
return 0;
}
}

void traceback(){
trail.clear();
while (!s.empty()){
s.pop();
}
node temp=v[v.size()-1];
while (temp.pre!=-1){
s.push(temp.ope);
temp=v[temp.pre];
}
while (!s.empty()){
trail.push_back(s.top());
s.pop();
}
}

void bfs(){
int done=0,res;
for (int i=1;i<=3;i++){
res=solve(temp.now,opes[i]);
if (flag[res]==0){
flag[res]=1;
if (res==((n+1)%k+k)%k){
if (temp.step+1<length){
length=temp.step+1;
traceback();
}
done=1;
break;
}
}
}
}
}

int main()
{
while(scanf("%d%d%d",&n,&k,&m)==3&&m!=0){
length=10000;

//无%
memset(flag,0,sizeof(flag));
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
flag[(n%k+k)%k]=1;
bfs();
//第一个是％
memset(flag,0,sizeof(flag));
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
v.push_back(node(((n%m+m)%m)%k,0,1,opes[4]));
flag[(n%k+k)%k]=1;
flag[((n%m+m)%m)%k]=1;
bfs();
//前两个是＊％
memset(flag,0,sizeof(flag));
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
v.push_back(node(((n*m)%k+k)%k,0,1,opes[3]));
v.push_back(node(0,1,2,opes[4]));
flag[(n%k+k)%k]=1;
flag[0]=1;
flag[((n*m)%k+k)%k]=1;
bfs();
if (length<10000){
printf("%d\n",length);
for (int i=0;i<trail.size();i++){
printf("%c",trail[i]);
}
}else{
printf("0");
}
printf("\n");
}
return 0;
}``````