PKU 1047解题报告(原创)
题目:Round and Round We Go1047
08-8-17
题目大意:
判断一个数是否为cyclic数.
一个数为cyclic的条件为:设数为n位数.那么原数乘以1~n所得的结果可以通过原来的数移位得到.

由于刚做完一个大数乘法的题,使用了对大数的处理方法.一次AC!

比如  142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142
142857就是一个cyclic数.
Description
A cyclic number is an integer n digits in length which, when multiplied by any integer from 1 to n, yields a"cycle"of the digits of the original number. That is, if you consider the number after the last digit to "wrap around"back to the first digit, the sequence of digits in both numbers will be the same, though they may start at different positions.For example, the number 142857 is cyclic, as illustrated by the following table:
142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142
Input
Write a program which will determine whether or not numbers are cyclic. The input file is a list of integers from 2 to 60 digits in length. (Note that preceding zeros should not be removed, they are considered part of the number and count in determining n. Thus, "01"is a two-digit number, distinct from "1" which is a one-digit number.)
Output
For each input integer, write a line in the output indicating whether or not it is cyclic.
Sample Input
142857
142856
142858
01
0588235294117647

Sample Output
142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic
代码如下
244k    0ms   AC
#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;
}

评论