pku 1046 高精度乘法+循环数.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;

//PKU 1046
//高精度乘法+循环数
#define NMAX 100
void mullow(int a[],int b,int ans[])
{
	int i,len;
	int tmp[NMAX]={0};
	len=a[0];
	for(i=1;i<=len;i++)
	{
		tmp[i]+=a[i]*b;
		tmp[i+1]=tmp[i]/10;
		tmp[i]%=10;
	}
	len++;
	while(tmp[len]>=10)
	{
		tmp[len+1] = tmp[len]/10;
		tmp[len] %=10;
		len++;
	}
	while(len>1 && tmp[len]==0) len--;
	tmp[0]=len;
	for(i=0;i<=tmp[0];i++) ans[i]=tmp[i];
}

int compare(int a[],int b[])
{
	int i;
	if(a[0]>b[0]) return 1;
	if(a[0]<b[0]) return -1;
	else
	{
		for(i=a[0];i>=1;i--)
		{
			if(a[i]>b[i]) return 1;
			if(a[i]<b[i]) return -1;
		}
		return 0;
	}
}

void solve(int a[])
{
	int i,j,k,t,flag,tt;
	int b[NMAX],c[NMAX];

	tt=1;
	for(i=1;i<=a[0];i++)
	{
		flag=0;
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		mullow(a,i,b);
//		for(j=b[0];j>=1;j--)
//			printf("%d",b[j]);
//		printf("\n");
		if(compare(a,b)==0) flag=1;
		else
		{
			for(j=2;j<=b[0];j++)
			{
				c[0]=b[0];
				for(k=j,t=0;k<=b[0];k++)
					c[++t]=b[k];
				for(k=1;k<j;k++)
					c[++t]=b[k];
				if(compare(a,c)==0) flag=1;
			}
		}
		if(flag==0) tt=0;
	}
	for(j=a[0];j>=1;j--)
		printf("%d",a[j]);
	if(1==flag)
		printf(" is cyclic\n");
	else
		printf(" is not cyclic\n");
}

int main()
{
	int a[NMAX],i,j;
	char str1[NMAX];
	while(scanf("%s",str1)!=EOF)
	{
		a[0]=strlen(str1);
		for(i=a[0]-1,j=1;i>=0;i--,j++) a[j]=str1[i]-'0';
//		for(j=a[0];j>=1;j--)
//			printf("%d",a[j]);
//		system("pause");
		solve(a);
	}
	return 0;

}