2013
11-27

# Remainder

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.

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.

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
*+

1. 题目中的modulus操作与计算机的%不同。modulus(a,b) = (a%b+b)%b。 即保证结果一定为正。而计算机中是先abs(a)%b，再把a符号付给它。

2. 在搜索过程中值会越来越大，不便于存入hash数组，由于计算的值总是用于比较modulus(tmp, K)==modulus(N+1,K)，因此我们可以不必保存tmp,而直接对tmp取modulus。

3. 由于存在modulus(tmp, M)的OP，因此要保证tmp一直还与M线性同余。取tmp = modulus(tmp,KM)，这样既可以保证tmp比较小，又保证与K,M都线性同余，使得之后的modulus(tmp,K)和modulus(tmp,M) 效果都与不对tmp进行任何处理效果相同。

4.注意Node中存的和hash的都是经过处理的tmp值。每次检查是否得到正确结果，需要检查 modulus(经过处理的tmp,K)==modulus(N+1,K)

import java.util.*;

public class Main {
String ops = "+-*%";
class Node {
int n;
String path;
}
int N, K, M, result, KM;
Scanner input = new Scanner(System.in);
boolean[] hash = new boolean[1000001];

public static void main(String[] args) {
new Main().work();
}

public int modulus(int a, int b) {
return (a % b + b) % b;
}

public void work() {
while (input.hasNext()) {
N = input.nextInt();
K = input.nextInt();
M = input.nextInt();
if (N == 0 && K == 0 && M == 0) {
break;
}
KM = K * M;
list.clear();
Arrays.fill(hash, false);
hash[modulus(N, KM)] = true;
result = modulus(N + 1, K);
bfs();
}
input.close();
}

public void bfs() {
while (!list.isEmpty()) {
Node node = list.poll();
if (modulus(node.n, K) == result) {
System.out.println(node.path.length());
System.out.println(node.path);
return;
}
for (int i = 0; i < ops.length(); i++) {
doOp(ops.charAt(i), node);
}
}
System.out.println(0);
}

public void doOp(char op, Node node) {
int tmp = 0;
switch (op) {
case '+':
tmp = modulus(node.n + M, KM);
break;
case '-':
tmp = modulus(node.n - M, KM);
break;
case '*':
tmp = modulus(node.n * M, KM);
break;
case '%':
tmp = modulus(modulus(node.n, M), KM);
break;
}
if (!hash[tmp]) {
hash[tmp] = true;
Node newNode = new Node();
newNode.path = node.path + op;
newNode.n = tmp;
}