hduProblem : 1104 ( Remainder )

Problem : 1104 ( Remainder )     Judge Status : Accepted
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta

#include<stdio.h>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

using namespace std;

struct cc

{

    int n,m;

};

string op[1005];

int step[1005];

int vis[1005],ans,k;

int main()

{

    int n,m,ok,flag;

    while(scanf("%d%d%d",&n,&k,&m)==3)

    {

        ok=0;

        if(!n&&!m&&!k)break;

        memset(step,0,sizeof(step));

        memset(vis,0,sizeof(vis));

        ans=(n+1+1000*k)%k;

        for(int i=0;i<=1001;i++)

            op[i].clear();

        queue <cc> q;

        cc c;

        c.m=(n+1000*m)%m;//注意n=-1和n=-1+10(k)做%运算结果不一样，所以事先存n%m;当以后遇到%时c.n=c.m%m；

        c.n=(n+1000*k)%k;

        q.push(c);

        vis[c.n]=1;

        while(!q.empty())

        {

            cc temp=q.front();

            q.pop();

            for(int i=0;i<4;i++)

            {

                cc u=temp;

                switch(i)

                {

                case 0:u.n=(u.n+m+1000*k)%k;break;

                case 1:u.n=(u.n-m+1000*k)%k;break;

                case 2:u.n=(u.n*m+1000*k)%k;u.m=0;break;//u.n*m后，u.n%m==0；以后遇到%运算后u.n==0!=u.m%m;

                case 3:u.n=(u.m+1000*k)%k;break;

                }

                if(!vis[u.n])

                {

                    step[u.n]=step[temp.n]+1;

                    vis[u.n]=1;

                    switch(i)

                    {

                    case 0:op[u.n]=op[temp.n]+'+';break;

                    case 1:op[u.n]=op[temp.n]+'-';break;

                    case 2:op[u.n]=op[temp.n]+'*';break;

                    case 3:op[u.n]=op[temp.n]+'%';break;

                    }

                    q.push(u);

                    if(u.n==ans){ok=1;flag=u.n;break;}   

                }

              

            }

              if(ok)break;   

        }

        if(!ok)printf("0\n");

        else

        {

            int t=0;

            printf("%d\n",step[flag]);

            cout<<op[flag]<<endl;

        }

    }

}