C语言程序设计漫谈之从n末尾有多少个0谈起.docx

C语言程序设计漫谈之从n末尾有多少个0谈起.docx

《C语言程序设计漫谈之从n末尾有多少个0谈起.docx》由会员分享，可在线阅读，更多相关《C语言程序设计漫谈之从n末尾有多少个0谈起.docx（31页珍藏版）》请在冰点文库上搜索。

C语言程序设计漫谈之从n末尾有多少个0谈起

从“n！

末尾有多少个0”谈起

   在学习循环控制结构的时候，我们经常会看到这样一道例题或习题。

问n！

末尾有多少个0？

POJ1401就是这样的一道题。

【例1】Factorial（POJ1401）。

Description

ThemostimportantpartofaGSMnetworkissocalledBaseTransceiverStation（BTS）.Thesetransceiversformtheareascalledcells（thistermgavethenametothecellularphone）andeveryphoneconnectstotheBTSwiththestrongestsignal（inalittlesimplifiedview）.Ofcourse,BTSesneedsomeattentionandtechniciansneedtochecktheirfunctionperiodically.

ACMtechniciansfacedaveryinterestingproblemrecently.GivenasetofBTSestovisit,theyneededtofindtheshortestpathtovisitallofthegivenpointsandreturnbacktothecentralcompanybuilding.Programmershavespentseveralmonthsstudyingthisproblembutwithnoresults.Theywereunabletofindthesolutionfastenough.Afteralongtime,oneoftheprogrammersfoundthisprobleminaconferencearticle.Unfortunately,hefoundthattheproblemissocalled"TravellingSalesmanProblem"anditisveryhardtosolve.IfwehaveNBTSestobevisited,wecanvisittheminanyorder,givingusN!

possibilitiestoexamine.Thefunctionexpressingthatnumberiscalledfactorialandcanbecomputedasaproduct1.2.3.4....N.ThenumberisveryhighevenforarelativelysmallN.

Theprogrammersunderstoodtheyhadnochancetosolvetheproblem.Butbecausetheyhavealreadyreceivedtheresearchgrantfromthegovernment,theyneededtocontinuewiththeirstudiesandproduceatleastsomeresults.Sotheystartedtostudybehaviourofthefactorialfunction.

Forexample,theydefinedthefunctionZ.ForanypositiveintegerN,Z（N）isthenumberofzerosattheendofthedecimalformofnumberN!

.Theynoticedthatthisfunctionneverdecreases.IfwehavetwonumbersN1

Input

ThereisasinglepositiveintegerTonthefirstlineofinput.Itstandsforthenumberofnumberstofollow.ThenthereisTlines,eachcontainingexactlyonepositiveintegernumberN,1<=N<=1000000000.

Output

ForeverynumberN,outputasinglelinecontainingthesinglenon-negativeintegerZ（N）.

SampleInput

6

3

60

100

1024

23456

8735373

SampleOutput

0

14

24

253

5861

2183837

（1）编程思路1。

n！

是一个很大的数，不能将其求出后，再统计其末尾0的个数。

由于10=2*5，且n!

中因子2的个数一定超过因子5的个数。

一个很容易想到的办法是：

对于1、2、3、…、n中的每一个数i求5的因子个数，然后将所有5的因子个数加起来就是n！

中末尾0的个数。

如何求一个数x含有的5的因子个数呢？

可以写成一个简单的循环。

cnt=0;

while（x%5==0）

{

cnt++;//x能被5整除，含有一个因子5，计数

x=x/5;//商有可能还含有因子5

}

这样，一个容易想到的解决办法的程序可写成一个二重循环，外循环控制从1~n，表示参与n!

计算的每个数，内循环对每个数，求其含有5的因子个数。

（2）源程序1-1。

#include

intmain（）

{

intt,n,cnt,i,x;

scanf（"%d",&t）;

while（t--）

{

scanf（"%d",&n）;

cnt=0;

for（i=1;i<=n;i++）

{

x=i;

while（x%5==0）

{

cnt++;

x/=5;

}

}

printf（"%d\n",cnt）;

}

return0;

}

这个源程序可以正确运行，但将其提交给POJ1401“Factorial”时，评测系统给出的结论是：

TimeLimitExceeded。

超时了，说明程序的效率不高。

有些同学想到，源程序中外循环for（i=1;i<=n;i++）从1~n。

但是1、2、3、4等不是5的倍数的数不可能含有5的因子呀，因此可将外循环修改为for（i=5;i<=n;i+=5），效率显然会提高些。

毕竟外循环次数只有原来的五分之一。

但将其再提交给POJ1401“Factorial”，评测系统给出的结论仍然是：

TimeLimitExceeded。

显然，要想不超时，可能的解决方法是将二重循环降成单重循环。

如何做呢？

（3）编程思路2。

以求100！

为例说明。

设先将1~100共100个数排成一行得到序列1。

且设保存5的因子个数的变量cnt的初值为0。

序列1:

12345678910……2122232425……95……99100

在序列1中，只有5、10、15、……、99、100共100/5=20个数中至少含有一个5的因子。

故cnt=cnt+n/5=0+20=20。

将序列1中的每个数除以5，只保留得到的整数，可排成序列2。

（对应操作为n=n/5）

序列2：

1234567891011121314151617181920

对应序列1的数为：

5101520253035404550555065607580859095100

在序列2中，有20个数，只有20/5=4个数含有因子5，即原序列中有4个数（25,50,75,100）至少含有两个因子5。

cnt=cnt+n/5=20+20/5=24。

再将序列2中的每个数除以5，只保留得到的整数，可排成序列3。

（对应操作为n=n/5）

序列31234

对应序列1的数为：

255075100。

此时，序列3中不再有数能被5整除，即原序列中没有数含有3个5的因子。

cnt=cnt+n/5=24+4/5=24。

至此，求得100！

末尾有24个0。

（4）源程序1-2。

#include

intmain（）

{

intt,n,cnt;

scanf（"%d",&t）;

while（t--）

{

scanf（"%d",&n）;

cnt=0;

while（n/5!

=0）

{

cnt=cnt+n/5;

n/=5;

}

printf（"%d\n",cnt）;

}

return0;

}

提交给POJ1401“Factorial”时，评测系统给出的结论是：

Accepted。

这个问题可以变形为较多的问题。

例如，求n!

能被7的最高多少次方整除？

（由于7是一个质数，所以求得n！

中含有因子7的个数就是问题的答案。

）；求n!

能被9的最高多少次方整除？

（由于9=3*3，因此不能直接求含有因子9的个数，先求出含有因子3的个数，再将得到的个数除以2取整就是问题答案。

）

POJ中问题2992“Divisors”与例1的解决思路有关，但复杂得多。

它求的是组合数c（n,k）的约数的个数，而组合数c（n,k）=n!

/[（n-k）!

*k!

]，因此问题会转化为求n!

中各素因子的个数。

为解决POJ2992这个问题，我们通过例子的形式先逐步解决一些相关的简单问题。

【例2】约数的个数。

输入正整数n，求n的约数的个数。

例如，输入24，24的约数有1、2、3、4、6、8、12、24共8个，因此输出8。

（1）编程思路。

最直接和简单的思路是用一个循环，将i从1~sqrt（n）逐个试探，若n%i==0，则i是n的约数，n/i也是n的约数，约数个数增加2个。

需要注意n是一个完全平方数的情况，此时约数个数只增加1。

（2）源程序。

#include

intmain（）

{

intn,cnt,i;

while（scanf（"%d",&n）&&n!

=0）

{

cnt=0;

for（i=1;i*i

{

if（n%i==0）

cnt+=2;

}

if（i*i==n）cnt++;

printf（"%d\n",cnt）;

}

return0;

}

【例3】分解质因数。

将一个正整数分解质因数。

例如：

输入90，输出90=2*3*3*5。

（1）编程思路1。

对整数n进行分解质因数，应让变量i等于最小的质数2，然后按下述步骤完成：

1）如果i恰等于n，则说明分解质因数的过程已经结束，输出即可。

2）如果n<>i，但n能被i整除，则应输出i的值，并用n除以i的商，作为新的正整数n，转第1）步。

3）如果n不能被i整除，则用i+1作为新的i值，转第1）步。

因此，程序主体是一个循环，在循环中根据n能否整除i，进行两种不同处理。

（2）源程序3-1及运行结果示例。

#include

intmain（）

{

intn,i;

while（scanf（"%d",&n）&&n!

=0）

{

printf（"%d=",n）;

i=2;

while（i

{

if（n%i==0）

{

printf（"%d*",i）;//i是n的因数，输出i

n=n/i;//对除以因数后的商再进行分解

}

else

i++;//找下一个因数

}

printf（"%d\n",n）;

}

return0;

}

运行源程序3-1，一个可能的运行示例如下：

90

90=2*3*3*5

120

120=2*2*2*3*5

0

从上面的运行示例可以看出，120分解质因数后，其因子2有3个，3有1个，5有1个。

如果要求输出形式为：

120=2^3*3^1*5^1，怎么修改呢？

（3）编程思路2。

源程序3-1中，在循环处理时若i是当前n的因子，立即输出因子，由于相同因子可能有多个，因此在每个因子输出前需要用一个循环对含因子i的个数进行统计，统计完后再输出。

并且为了方便后面使用，程序中将因子及其相应个数均用数组保存起来。

（4）源程序3-2及运行示例。

#include

intmain（）

{

intn,i,cnt,len;

intp[100],e[100];

while（scanf（"%d",&n）&&n!

=0）

{

printf（"%d=",n）;

len=0;

for（i=2;i*i<=n&&n>1;i++）

{

if（n%i==0）//i是n的因子

{

cnt=0;

while（n%i==0）

{

n/=i;

cnt++;

}

p[len]=i;//保存因子i

e[len++]=cnt;//保存因子i的个数

}

}

if（n>1）{p[len]=n;e[len++]=1;}

for（i=0;i

printf（"%d^%d*",p[i],e[i]）;

printf（"%d^%d\n",p[len-1],e[len-1]）;

}

return0;

}

运行源程序3-1，一个可能的运行示例如下：

90

90=2^1*3^2*5^1

120

120=2^3*3^1*5^1

0

【例4】DiophantusofAlexandria（POJ2917）。

Description

DiophantusofAlexandriawasanEgyptmathematicianlivinginAlexandria.Hewasoneofthefirstmathematicianstostudyequationswherevariableswererestrictedtointegralvalues.Inhonorofhim,theseequationsarecommonlycalledDiophantineequations.OneofthemostfamousDiophantineequationisxn+yn=zn.Fermatsuggestedthatforn>2,therearenosolutionswithpositiveintegralvaluesforx,yandz.Aproofofthistheorem（calledFermat’slasttheorem）wasfoundonlyrecentlybyAndrewWiles.

ConsiderthefollowingDiophantineequation:

Diophantusisinterestedinthefollowingquestion:

foragivenn,howmanydistinctsolutions（i.e.,solutionssatisfyingx≤y）doesequation

（1）have?

Forexample,forn=4,thereareexactlythreedistinctsolutions:

Clearly,enumeratingthesesolutionscanbecometediousforbiggervaluesofn.CanyouhelpDiophantuscomputethenumberofdistinctsolutionsforbigvaluesofnquickly?

Input

Thefirstlinecontainsthenumberofscenarios.Eachscenarioconsistsofonelinecontainingasinglenumbern（1≤n≤109）.

Output

Theoutputforeveryscenariobeginswithalinecontaining“Scenario#i:

”,whereiisthenumberofthescenariostartingat1.Next,printasinglelinewiththenumberofdistinctsolutionsofequation

（1）forthegivenvalueofn.Terminateeachscenariowithablankline.

SampleInput

2

4

1260

SampleOutput

Scenario#1:

3

Scenario#2:

113

（1）编程思路。

这个问题是：

已知n，求丢番图方程1/n=1/x+1/y的整数解有多少组？

因为1/n=1/x+1/y

所以n=（x*y）/（x+y）

（x+y）*n=x*y

设x=n+a;y=n+b,可得n*n=a*b

题目就转化成了求所有整数对（a,b），使得a*b=n*n。

即求n*n的约数个数，由于约数都是成对出现的，两数乘积为n*n。

注意：

n与n成对出现，而只计算了1次。

因此，为避免重复，设n*n的约数个数为p，（p+1）/2即为所求。

因此，本题的关键是要求出n*n的约数的个数。

按照例2中的源程序采用的方法来解决这个问题不现实。

因为：

1）给定n的范围是1≤n≤109，n可能是一个很大的整数，n*n可能超出一个int型整数表数范围；2）即使采用64位整数避免了溢出的问题，但由于给定n可能很大，例2的源程序从i=2到i=sqrt（n）逐个试探，效率不高，会超时。

因此，我们采用约数定理来求约数的个数。

设n可以分解质因数：

n=p1^e1×p2^e2×p3^e3×…×pk^ak,

由约数定义可知p1^e1的约数有：

p1^0,p1^1,p1^2......p1^e1，共（e1+1）个；同理p2^e2的约数有（e2+1）个......pk^ek的约数有（ek+1）个。

故根据乘法原理：

n的约数的个数就是（e1+1）（e2+1）（e3+1）…（ek+1）。

有了例3分解质因数的基础，在加上这个定理，就很容易求n*n的约数个数了。

（2）源程序4-1。

#include

intmain（）

{

intt,k,n,cnt,len,i,ans;

inte[101];

scanf（"%d",&t）;

for（k=1;k<=t;k++）

{

scanf（"%d",&n）;

len=0;

for（i=2;i*i<=n&&n>1;i++）

{

if（n%i==0）

{

cnt=0;

while（n%i==0）

{

n/=i;

cnt++;

}

e[len++]=cnt;

}

}

if（n>1）e[len++]=1;

ans=1;

for（i=0;i

{

ans*=（2*e[i]+1）;//e[i]保存的是n的因子i的个数，显然n*n得2倍

}

printf（"Scenario#%d:

\n%d\n\n",k,（ans+1）/2）;

}

return0;

}

（3）换一种思路编写源程序。

由于n可能很大，而将n分解质因数时，因子一定是一个质数，因此，我们可以先将sqrt（max_n）以内的质数先都求出来，这样试探因子时直接从2开始的质数一个一个找，会提高执行效率的。

质数表的构造采用筛法来完成。

直接给出源程序如下：

#include

#definemaxn34000//34000*34000=1156000000>10e9

intvis[maxn];

intprime[maxn],prime_cnt;

voidget_prime（）//筛法预处理出素数表

{

inti,j;

for（i=0;i

vis[0]=vis[1]=0;

prime_cnt=0;

for（i=2;i

{

if（vis[i]）

{

prime[prime_cnt++]=i;

if（i*i<=maxn）

{

for（j=i*i;j

vis[j]=0;

}

}

}

}

intmain（）

{

intt,n,cnt,len,i,k,ans;

inte[101];

get_prime（）;

scanf（"%d",&t）;

for（k=1;k<=t;k++）

{

scanf（"%d",&n）;

len=0;

for（i=0;i1;i++）

{

if（n%prime[i]==0）

{

cnt=0;

while（n%prime[i]==0）

{

n/=prime[i];

cnt++;

}

e[len++]=cnt;

}

}

if（n>1）e[len++]=1;

ans=1;

for（i=0;i