nyoj517 最小公倍数 (大数)
发布时间:2020-12-14 01:16:45 所属栏目:大数据 来源:网络整理
导读:描述 为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。 但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。 事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。 我们希望寻找到能除尽1至n的的每个数字的最小整数m. 输入
为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。
但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。
事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数m.
我第一次写出来的是大数n的阶乘,想想不对,因为n为4,4的阶乘为24,而题意是找4以内的最小公倍数 是12,然后参考了一篇博客的一个思路,先把2-n之间的因子去掉,如n==6时,2,6,去除后为 2,1,然后在按照大数相乘那样做 参考思路来源http://blog.csdn.net/qq_32650831/article/details/51328910 代码: #include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
char a[102]={0},b[102][10000];
int k=2;
void js(int x)//大数乘法
{
int cx=0,cb=0,i,j,t[3],s[10000]={0};
cb=strlen(b[k]);
if (x/10==0)
{
t[0]=x;
cx=1;
}
else if (x/100==0)
{
t[0]=x/10;
t[1]=x%10;
cx=2;
}
else
{
t[0]=x/100;
t[1]=x/10%10;
t[2]=x%10;
cx=3;
}
for (i=0;i<cb;i++)
for (j=0;j<cx;j++)
{
s[i+j+1]+=(b[k][i]-'0')*t[j];
}
for (i=cb+cx-1;i>=0;i--)
{
if (s[i]>=10)
{
s[i-1]+=s[i]/10;
s[i]%=10;
}
}
i=0;
while (s[i]==0)
{
i++;
}
k++;
for (j=0;i<cx+cb;i++,j++)
{
b[k][j]=s[i]+'0';
}
b[k][j]=' ';
}
int main()
{
int n,j;
strcpy(b[2],"2");
for (i=2;i<101;i++)
{
a[i]=i;
}
for (i=2;i<101;i++)//将因子去除
for (j=i+1;j<101;j++)
{
if (a[j]%a[i]==0)
a[j]=a[j]/a[i];
}
for(i=3;i<101;i++)
{
js(a[i]);
}
while (cin>>n)
{
if (n==0)
cout<<1<<endl;
else if (n==1||n==2)
cout<<n<<endl;
else
{
cout<<b[n]<<endl;
}
}
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |