hdu1104Remainder

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <string>
 6 #include 
 7 using namespace std;
 8 char str[4]={‘+‘,‘-‘,‘*‘,‘%‘};
 9 int n,k,m;
10 bool vis[200000];
11 struct node
12 {
13     int num;
14     int step;
15     string st;
16 }st1,st2;
17 
18 void bfs()
19 {
20     memset(vis,false,sizeof(vis));
21     queueq;
22     st1.num=n;
23     st1.step=0;
24     st1.st="";
25     q.push(st1);
26     vis[((n%k)+k)%k]=true;
27     while(!q.empty())
28     {
29        st2=q.front();
30        q.pop();
31        if(((n+1)%k+k)%k==((st2.num%k)+k)%k)
32        {
33            printf("%d\n",st2.step);
34            cout<endl;
35            return ;
36        }
37        for(int i=0; i<4; i++)
38        {
39            if(i==0)
40            {
41                st1.num=(st2.num+m)%(k*m);
42                st1.st=st2.st+‘+‘;
43            }
44            else if(i==1)
45            {
46                st1.num=(st2.num-m)%(k*m);
47                st1.st=st2.st+‘-‘;
48            }
49            else if(i==2)
50            {
51                st1.num=(st2.num*m)%(k*m);
52                st1.st=st2.st+‘*‘;
53            }
54            else
55            {
56                st1.num=(st2.num%m+m)%m%(k*m);
57                st1.st=st2.st+‘%‘;
58            }
59            st1.step=st2.step+1;
60            if(!vis[(st1.num%k+k)%k])
61            {
62                q.push(st1);
63                vis[(st1.num%k+k)%k]=true;
64            }
65        }
66     }
67     printf("0\n");
68 }
69 
70 int main()
71 {
72     while(scanf("%d%d%d",&n,&k,&m)!=EOF)
73     {
74         if(n==0&&k==0&&m==0) break;
75         bfs();
76     }
77     return 0;
78 }