Question

用C++编写求N的阶乘最后面的非零位的程序(N很大)！

Answer 1

/*

阶乘最后一位非零数

*/

#include"bits/stdc++.h"

usingnamespacestd;

intexgcd(inta,intb,int&x,int&y,intc)

{

if(b==0)

{

x=c;

y=0;

returna;

}

intd=exgcd(b,a%b,x,y,c);

intt=x;

x=y;

y=t-a/b*y;

returnd;

}

intmain()

{

longlongfac[10]={1,1,2,6,24};

longlongN;

while(cin>>N)

{

intk=0;

longlongans=1;

while(N)

{

k+=N/5;

ans*=fac[N%5];

ans%=5;

N/=5;

}

k%=4;

ans*=1<<k;

ans%=5;

intx,y;

exgcd(5,2,x,y,-ans);

intres=x*5+ans;

res=(res%10+10)%10;

cout<<res<<endl;

}

}

扩展资料

阶乘亦递归方式定义：0!=1，n!=(n-1)!×n

#include<stdio.h>

intmain()

{

intn,i;

unsignedlonglongfactorial=1;

printf("输入一个整数:");

scanf("%d",&n);

//如果输入是负数，显示错误

if(n<0)

printf("Error!负数没有阶乘jiechen");

else

{

for(i=1;i<=n;++i)

{

factorial*=i;//factorial=factorial*i;

}

printf("%d!=%llu",n,factorial);

}

return0;

}

参考资料来源：百度百科—c语言

Answer 2

#include<stdio.h>
void main()
{
int a=1,i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
a=a*i;
while(a%10==0)a=a/10;
a=a%10;
}
printf("%d\n",a);
}

追问

我跟你做的是一样的，但是这种方法在某种情况，会出现错误，你能解释一下吗？

追答

在什么情况下，我还没发现，你举个例子

追问

例子，我举不出来诶！是提交的时候，内测数据的第十一个错啦！呵呵！有点恼火！我看不到内测数据，所以。。。但是用直接求阶乘取余的方法，就能通过啦！

追答

我先把这道题看得太简单了，我那个程序的确有错，下面是我改过的程序，这次应该对了
#include
#include
void main()
{
int n,i,o,k=0,l=0,m=1,r,f;
scanf("%d",&n);
if(n==1){printf("1\n");exit(0);}
for(i=1;i<=n;i++)
{
o=i;
l=0;
while(o%2==0)
{
o=o/2;
k=k+1;
}
while(o%5==0)
{
o=o/5;
l=l+1;
}
k=k%4-l%4;
if(k<0)k=k+4;
m=(m*o)%10;

}
switch(k%4)
{
case 0:r=6;break;
case 1:r=2;break;
case 2:r=4;break;
case 3:r=8;break;
}
f=(m*r)%10;
printf("%d\n",f);
}

追问

看不懂诶！你能在关键语句后面加上必要的注释吗？

追答

#include
#include
void main()
{
int n,i,o,k=0,l=0,m=1,r,f;
scanf("%d",&n);
if(n==1){printf("1\n");exit(0);} /*n=1时直接输出1，然后终止程序*/
for(i=1;i<=n;i++)
{
o=i;
l=0;
while(o%2==0)
{
o=o/2;
k=k+1; /*k为i中因数2的个数*/
}
while(o%5==0)
{
o=o/5;
l=l+1; /*l为i中因数5的个数*/
}
k=k%4-l%4; /*k-l为因数2*5（即10）的个数，后面用上的只有2^k的个位，所以为了尽量
减小k的值，令k和l都除4取余数后相减，取4为模的原因是2^k从k=1开始个位一次为2、4、8、6、
2、4、8、6……，循环节为4*/
if(k<0)k=k+4;
m=(m*o)%10;

}
switch(k)
{
case 0:r=6;break; /*2^4个位为6，所以r=6*/
case 1:r=2;break; /*2^1个位为2，所以r=2*/
case 2:r=4;break; /*2^2个位为4，所以r=4*/
case 3:r=8;break; /*2^3个位为8，所以r=8*/
}
f=(m*r)%10;
printf("%d\n",f);
}
/*我的思路是让n!把所有因数2和因数5都除去后，再让这个数乘以2^(因数2与因数5差)（因数2的个数总
是大于因数5的个数）中间计算时能减小的数都减小*/
我才学C++，这还我是第一次写注释，可能写得不好，不懂的再问我