时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。
但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。
事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数m.
输入多组测试数据(少于500组)。 每行只有一个数n(1<=n<=100).输出输出相应的m。样例输入234样例输出2612来源2011蓝桥杯上传者杨延玺 暴力法+大数+欧几里得+数论
#include<cstring>
#include<cstdio>
using namespace std ;
const int maxn=80;
const int Nin=100;
int arr[502][maxn+3];
int save[maxn+3];
int temp[maxn+3];
void swap(int *a,int *b)
{
*a+=*b;
*b=*a-*b;
*a=*a-*b;
}
void func()
{
int i,j,s,c,b,temp1,r;
memset(arr,0,sizeof(arr));
memset(save,0,sizeof(save));
memset(temp,0,sizeof(temp));
arr[0][0]=1;
arr[1][0]=2;
arr[2][0]=6;
*save=6;
for(i=4;i<=Nin;i++) //1-100打表求出来
{
c=0,b=i;
for(j=0;j<maxn ;j++)
{
temp[j]=save[j];
}
for(j=maxn-1;j>=0;j--)
{
s=temp[j]+c;
c=(s%b)*10 ;
if(j!=0) temp[j]=s/b;
else if(j==0)temp[j]=s; //大数求余数
}
temp1=temp[0];
if(temp1!=0)
{
c=0;
for(j=0;j<maxn;j++) //大数相除
{
s=save[j]*i+c;
save[j]=s%10;
c=s/10;
}
if(temp1<b)
{
swap(temp1,b);
}
while(r=temp1%b)
{
temp1=b;
b=r;
}
c=0;
for(j=maxn-1;j>=0;j--)
{
s=save[j]+c;
c=(s%b)*10 ;
save[j]=s/b;
}
}
for(j=0;j<maxn;j++)
{
arr[i-1][j]=save[j];
}
}
}
int main( void )
{
int n,i;
func();
while(cin>>n)
{
for( i=maxn ; arr[n-1][i]==0 ; i-- ) ;
for(;i>=0;i--)
cout<<arr[n-1][i];
cout<<endl;
}
return 0;
}