登山之道

http://acm.pku.edu.cn/JudgeOnline/problem?id=1047
#include <cstdlib>
#include <iostream>

using namespace std;

typedef struct  
{//存放大整数.题目要求为60位,必须自己定义
    int digits[100];
    int len;
}big;

big  getone(char str[100])
{//将输入的字符串转换成big类型并返回
    big res;
    int len=strlen(str);
    res.len=len;
    for(int i=0;i<len;i++)
    {
        res.digits[len-i-1]=str[i]-'0';//数在digits中倒序存储
    }
    return res;
}

big  mult(big b,int c)
{//大整数的乘法
    big res;
    res.len=b.len;
    memset(res.digits,0,sizeof(res.digits));
    for (int i=0;i<res.len;i++)
    {
        res.digits[i]+=b.digits[i]*c;//乘法处理.结果每一位不一定都是1位
    }
    for (int i=0;i<res.len;i++)
    {
        if (res.digits[i]>9)
        {
            res.digits[i+1]+=res.digits[i]/10;//处理进位
            res.digits[i]=res.digits[i]%10;//模除,余数为该为上的数
            while(res.digits[res.len]!=0) res.len++;
        }
    }
    return res;
}

bool  add_one(big  b)
{//剪枝处理
    //剪枝原理:原数*(数长+1)=99….9(长度为原数长度+1)
    big one;
    one.len=0;
    memset(one.digits,0,sizeof(one.digits));
    one=mult(b,b.len+1);
    if(one.len>b.len)
        return 0;
    else
    {
        one.digits[0]+=1;
        for (int i=0;i<one.len;i++)
        {
            if (one.digits[i]>9)
            {
                one.digits[i+1]+=one.digits[i]/10;
                one.digits[i]=one.digits[i]%10;
                while(one.digits[one.len]!=0) one.len++;
            }
        }
        if(one.len!=b.len+1)//如果为999...9形式,加1后必进位,因此不需要继续判断
            return 0;
        else
            return 1;
        
    }
    return 0;
}

big move_one(big b)
{//将big类型的数向左移动一位.原来的第一位放到最后一位.用于和原数比较
    int len=b.len;
    int a=b.digits[0];
    for (int i=0;i<len-1;i++)
    {
        b.digits[i]=b.digits[i+1];
    }
    b.digits[len-1]=a;
    return b;
}

bool comp(big b,big c)
{//不叫两个big类型的数是否相等.相等返回1,否则返回0
    bool a=1;
    if (b.len!=c.len)
        a=0;
    else
    {
        for (int i=0;i<b.len;i++)
        {
            a=a&&(b.digits[i]==c.digits[i]);
            if(!a)
                return a;
        }
    }
    return a;
}

int main(int argc, char *argv[])
{
    char str[100];
    bool a=0;//标记!
    while (cin>>str)//处理输入
    {
        big one;
        one=getone(str);
        if(!add_one(one))//剪枝,可以剪除99%的非数cyclic数
        {
            a=0;
        }
        else
        {
            big two=one;
            for (int i=1;i<one.len;i++)
            {
                two=mult(one,i+1);
                for (int j=0;j<one.len;j++)
                {    
                    two=move_one(two);//每移动一次,比较一次
                    a=a || comp(two,one);//只要一次比较成功,就将a设置为1表示成功
                    if(a)
                        break;
                }
            }
        }
        if(a)
            cout<<str<<" is cyclic"<<endl;
        else
            cout<<str<<" is not cyclic"<<endl;
    }

    //system("PAUSE");
    //return EXIT_SUCCESS;
}