POJ 1047Round and Round We Go——大数乘法+匹配

题目链接点击打开链接

题意：给定一个n位数，判断该数乘以i (1<=i<=n)是否还由该数的各个位上的数通过改变顺序组成。

思路：很明显，题中的数的位数最多60位，显然要用到大数乘法。不过，这道题是一个大数乘以一个小数，比较简单。如果乘以i后位数变大了，很明显该数就不是cyclic。在位数相同的情况下再判断。只要将得到的大数sort一下，再和初始给的数sort以后的值一位一位比较就可以了。easy~~~

开始时把给的数直接sort了。。。傻逼掉了

AC代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cmath>
using namespace std;
int tmp[100],a[1000],acopy[1000],len;
bool multi(int n)//大数乘法
{
    int i,t=0;
    for(i=0; i<len; i++)
    {
        t=a[i]*n+t;
        tmp[i]=t%10;
        t/=10;
    }
    if(t>0) return false;//判断最后是否会进位
    return true;
}

bool judge(int n)
{
    if(!multi(n))//有进位直接返回false
        return false;
    sort(tmp,tmp+len);//开始匹配~~~
    for(int i=0; i<len; i++)
        if(tmp[i]!=acopy[i])
            return false;
    return true;
}
int main()
{
    char num[1000];
    while(scanf("%s",num)!=EOF)
    {
        int cnt=0,flag=1;
        len=strlen(num);
        for(int i=len-1; i>=0; i--)
        {
            a[cnt]=num[i]-'0';
            acopy[cnt]=a[cnt];
            cnt++;
        }
        sort(acopy,acopy+len);//将给定的数sort
        for(int i=2; i<=len; i++)
        {
            if(!judge(i))
            {
                flag=0;
                printf("%s is not cyclicn",num);
                break;
            }
        }
        if(flag)    printf("%s is cyclicn",num);
    }
    return 0;
}