Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!

Project Euler——Problem 29

原题与答案：

Problem 29

25 October 2002

Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(5)=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤100?

Answer:9183

 

分析与解答：

题目的意思是由在[2,100]区间中的a和b由a^b形式构成的数有多少个。首先我们先确定一点，那就是a_1^{b_1}=a_2^{b_2}这样的情况是存在的，比如2^4=4^2，那么也就是说有重复的数值存在，其次是我们是否需要求出每一个数值的具体大小呢？答案是否定的，在[2,100]区间中，我们得到的最大数值是100^{100}，大概有201位，直接去算那么数值比较大，而且比较也很久，我们就要想换一种方法。我们利用一个更快的方法来进行，假设a的质因素分解形式是a=p_1^{s_1}*p_2^{s_2}*...*p_k^{s_k}，那么a^b=p_1^{b*s_1}*p_2^{b*s_2}*...*p_k^{b*s_k}，我们可以将所有的数值都化成质因素分解的形式，这样我们只需要比较对应的次数，而且在100内的素数只有25个，比较的个数比较少。每次我们分解出a的形式，然后对于a^b只要将次数都乘以b，就可以了，最后将这些次数序列排个序，计算有多少种即可，我的源程序代码如下所示：

 

  1. #include<stdio.h>
  2. #include<memory.h>
  3. #include<algorithm>
  4. bool nprime[101];
  5. int a[26],i,j,k,n,ans,temp[25];
  6. struct node
  7. {
  8.         int list[25];
  9. }res[9801];
  10. bool cmp(node s,node t)
  11. {
  12.         return memcmp(s.list,t.list,sizeof(res[0].list))<0;
  13. }
  14. void calc(int s)
  15. {
  16.         int i;
  17.         for (i=1;i<=a[0];i++)
  18.         {
  19.                 temp[i-1]=0;
  20.                 while (s%a[i]==0)
  21.                 {
  22.                         s/=a[i];
  23.                         temp[i-1]++;
  24.                 }
  25.         }
  26. }
  27. int main()
  28. {
  29.         a[0]=0;
  30.         memset(nprime,false,sizeof(nprime));
  31.         for (i=2;i<=100;i++)
  32.                 if (!nprime[i])
  33.                 {
  34.                         a[++a[0]]=i;
  35.                         if (i<=10)
  36.                                 for (j=i*i;j<=100;j+=i)
  37.                                         nprime[j]=true;
  38.                 }
  39.         n=0;
  40.         for (i=2;i<=100;i++)
  41.         {
  42.                 calc(i);
  43.                 for (j=2;j<=100;j++)
  44.                 {
  45.                         for (k=0;k<a[0];k++)
  46.                                 res[n].list[k]=temp[k]*j;
  47.                         n++;
  48.                 }
  49.         }
  50.         std::sort(res,res+n,cmp);
  51.         ans=0;
  52.         for (i=j=0;;)
  53.         {
  54.                 ans++;
  55.                 while (j<n&&!memcmp(res[i].list,res[j].list,sizeof(res[0].list))) j++;
  56.                 if (j==n) break;
  57.                 i=j;
  58.         }
  59.         printf("%d\n",ans);
  60.         return 0;
  61. }

 

 

Prject Euler Comments(0) 2009年7月27日 18:58

Project Euler——Problem 28

原题与答案：

Problem 28

11 October 2002

 

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

Answer:669171001
 

分析与解答：

这题是求按照顺时针从中间展开的1001*1001的方阵对角线上数字的和，其实很简单，最初想法肯定是先列出这个方阵，然后求，但是实际上不用，我们一圈一圈来看，除了最里圈只有一个数字1外，其余都是四个数字，而且实际上沿着1向右上角走去是奇数的平方，那么我们可以根据[2*(k+1)-1]^2-(2*k-1)^2=(2*k+1)^2-(2*k-1)^2=8*k对角线上的最大数值的差是8乘以圈数-1，这样我们对于每一圈处理四个数值即可，最后便能很轻松得到结果，我的源程序代码如下所示：

 

  1. #include<stdio.h>
  2. int i,j,ans;
  3. int main()
  4. {
  5.         ans=1;
  6.         for (i=1,j=2;i<1002001;i+=4*j,j+=2) ans+=i*4+j*10;
  7.         printf("%d\n",ans);
  8.         return 0;
  9. }

 

 

Prject Euler Comments(1) 2009年7月27日 17:58

Project Euler——Problem 27

原题与答案：

Problem 27

27 September 2002

 

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

 

Answer:-59231
 

分析与解答：

题目是求两个系数a和b，使得他们构成式子n^2+a*n+b，然后将n从0开始取值，直到不是素数为止，现在我们要在a和b的绝对值都在1000内的范围中找出能够令n取到最大的a和b，输出他们的乘积。本身这个题目不难，重点在于枚举和素数的判定，我们列一个素数表即可，考虑到题目中的提示，79的n已经是比较大的了，我们根据这个范围大概列了90000以内的素数表，然后穷举a和b，整个过程十分简单，我的源程序代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int ansa,ansb,ansn,a,b,n,i,j;
  4. bool nprime[90001];
  5. int calc(int a,int b)
  6. {
  7.         int i,s;
  8.         for (i=0;;i++)
  9.         {
  10.                 s=i*i+i*a+b;
  11.                 if (s<2||nprime[s]) break;
  12.         }
  13.         return i-1;
  14. }
  15. int main()
  16. {
  17.         memset(nprime,false,sizeof(nprime));
  18.         for (i=2;i<=300;i++)
  19.                 if (!nprime[i])
  20.                         for (j=i*i;j<=90000;j+=i)
  21.                                 nprime[j]=true;
  22.         ansn=-1;
  23.         for (a=-999;a<=999;a++)
  24.                 for (b=-999;b<=999;b++)
  25.                 {
  26.                         n=calc(a,b);
  27.                         if (n>ansn)
  28.                         {
  29.                                 ansa=a;
  30.                                 ansb=b;
  31.                                 ansn=n;
  32.                         }
  33.                 }
  34.         printf("%d\n",ansa*ansb);
  35.         return 0;
  36. }

 

 

 

Prject Euler Comments(2) 2009年7月27日 17:29

Project Euler——Problem 26

原题与答案：

Problem 26

13 September 2002

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

^(1)/_(2) =  0.5
^(1)/_(3) =  0.(3)
^(1)/_(4) =  0.25
^(1)/_(5) =  0.2
^(1)/_(6) =  0.1(6)
^(1)/_(7) =  0.(142857)
^(1)/_(8) =  0.125
^(1)/_(9) =  0.(1)
^(1)/_(10) =  0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ^(1)/_(7) has a 6-digit recurring cycle.

Find the value of d < 1000 for which ^(1)/_(d) contains the longest recurring cycle in its decimal fraction part.

Answer:983

 

分析与解答：

这个题目是求在1000内的某个整数，其循环节最长。这个题目其实是很简单的，先说说常规算法，常规的方法直接想到的是列出各个位数，然后强行判定循环节，这样算法的复杂度十分的高，等待必然也是很漫长的。我们可以换个角度考虑，利用数学知识来想问题，从除法的运算法则入手，我们做除法无非就是每次将上次的余数乘以10然后再对除数取余，如此往复，那么循环节有什么特点呢？当前的余数相同！相同的余数必然引出一个相同的商序列，也就是我们的结果数字排列，因此我们的算法就非常简单了，先利用一个数值表示每次的余数，一直取余直到其重复出现为止，此时两次出现的距离就是我们的循环节了。那么我们需要最多判断多少次呢？根据取余规则我们可以肯定是不超过除数自身的非负整数，因此规模实际上十分的小，这题可以很轻松的解决，下面是我的程序源代码：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int i,ans,best,t,fir[1000];
  4. int calc(int s)
  5. {
  6.         int i,mod=1;
  7.         memset(fir,-1,sizeof(fir));
  8.         for (i=0;;i++)
  9.         {
  10.                 mod=(mod*10)%s;
  11.                 if (fir[mod]==-1) fir[mod]=i;
  12.                 else return i-fir[mod];
  13.         }
  14. }
  15. int main()
  16. {
  17.         ans=0;
  18.         best=0;
  19.         for (i=1;i<1000;i++)
  20.         {
  21.                 t=calc(i);
  22.                 if (t>best)
  23.                 {
  24.                         best=t;
  25.                         ans=i;
  26.                 }
  27.         }
  28.         printf("%d\n",ans);
  29.         return 0;
  30. }

 

 

Prject Euler Comments(0) 2009年7月27日 16:43

Project Euler——Problem 25

原题与答案：

Problem 25

30 August 2002

The Fibonacci sequence is defined by the recurrence relation:

F_(n) = F_(n-1) + F_(n-2), where F_(1) = 1 and F_(2) = 1.

Hence the first 12 terms will be:

F_(1) = 1
F_(2) = 1
F_(3) = 2
F_(4) = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Answer:4782

 

分析与解答：

这个题目是求斐波那契数列的第几项开始是不小于1000位的，先整体估计一下，由于一个数s的位数为\lfloor s \rfloor +1，那么根据斐波那契数列的通项公式F_n=\dfrac{({\dfrac{1+\sqrt{5}}{2}})^n-({\dfrac{1-\sqrt{5}}{2}})^n}{\sqrt{5}}，大概估计一下\lfloor F_n \rfloor +1的范围，不是很大，在我们可以容忍的范围之内，于是我们可以利用高精度来进行计算，当然我们计算某一项的时候需要的值只有前两项，于是我们可以辗转迭代，最后就能获得结果，具体实现的源代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int f[2][2000],i,j,t,x;
  4. int main()
  5. {
  6.         memset(f,0,sizeof(f));
  7.         f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;
  8.         for (i=3;;i++)
  9.         {
  10.                 t=0;
  11.                 x=1-(i&1);
  12.                 f[x][0]=f[1-x][0];
  13.                 for (j=1;j<=f[1-x][0];j++)
  14.                 {
  15.                         f[x][j]+=t+f[1-x][j];
  16.                         if (f[x][j]>=10)
  17.                         {
  18.                                 t=1;
  19.                                 f[x][j]-=10;
  20.                         }
  21.                         else t=0;
  22.                 }
  23.                 if (t) f[x][++f[x][0]]=1;
  24.                 if (f[x][0]>=1000) break;
  25.         }
  26.         printf("%d\n",i);
  27.         return 0;
  28. }

 

 

Prject Euler Comments(0) 2009年7月25日 08:39

Project Euler——Problem 24

原题与答案：

Problem 24

16 August 2002

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Answer:2783915460

 

分析与解答：

这个题目是求10个数（0到9）的第1000000个字典序排列是多少，本身由于10!=3628800，完全在我们的承受范围之内，所以你可以直接枚举，但是这样做的复杂度是O(n!)，在个数比较多的时候就是一场噩梦，我们利用一种复杂度是O(n^2)的算法来完成这题。首先我们来分析一下，当前面的某些位数确定后，其实以他们为前缀的排列是令他们固定，然后将剩下的数值进行全排列，也就是说对于一个第k大的排列，我们从左到右确定某个位的数值时候只要判定对于这个数值位右边的全排列。假设右边有s位，那么固定第s+1位的数值就有s!种排列，于是乎我们等于是在找未使用过的第\dfrac{k-1}{s!}大数值（之所以是k-1是要防止他被s!整除，使得后面出现第0大的数的情况），于是便有了如下的程序源代码：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. bool yet[10];
  4. int i,j,s,fac[10];
  5. int main()
  6. {
  7.         fac[0]=1;
  8.         for (i=1;i<=9;i++)
  9.                 fac[i]=fac[i-1]*i;
  10.         memset(yet,false,sizeof(yet));
  11.         s=1000000;
  12.         for (i=9;i>=0;i--)
  13.                 for (j=0;;)
  14.                         if (yet[j]) j++;
  15.                         else
  16.                                 if (s>fac[i])
  17.                                 {
  18.                                         s-=fac[i];
  19.                                         j++;
  20.                                 }
  21.                                 else
  22.                                 {
  23.                                         printf("%d",j);
  24.                                         yet[j]=true;
  25.                                         break;
  26.                                 }
  27.         printf("\n");
  28.         return 0;
  29. }

 

 

Prject Euler Comments(0) 2009年7月25日 08:06

Project Euler——Problem 23

原题与答案：

Problem 23

02 August 2002

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Answer:4179871

 

分析与解答：

题目中先定义了一种数，这种数的特点是他的所有小于本身的约数的和大于本身，然后阐述了一个结论，任何一个大于28123的整数都能写成两个这种数的和，要我们求不能写成两个这种数的和的数的总和。很自然地我们想到了一种解法，先枚举所有的那种数，然后获得所有小等于28123的两个这种数的和，最后把没出现的全部加起来就可以了。首先是这种数的枚举，由于12是最小的，所以枚举到28111即可，对于每个数判断小于他的约数的和是否大于本身。那么约数怎么求呢？在前面的文章中我们已经说过了，就是质因数分解，然后利用公式求得，这里就不再重复了，这样我们就能枚举出这些数了。最后我们要做的是求出所有是两个这种数的和的数。我们用一个bool数组表示一个数是否可以表示为两个这种数的和，然后我们利用二次时间把所有可以表示为两个这种数和的数标示，最后线型扫描一次就能完成任务了。我的程序员代码如下所示：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. bool nprime[168],can[28112];
  4. int a[50],s[7000],i,j,ans;
  5. int calc(int s)
  6. {
  7.         int i,ret=1,t;
  8.         for (i=1;s!=1&&i<=a[0];i++)
  9.         {
  10.                 t=1;
  11.                 while (s%a[i]==0)
  12.                 {
  13.                         s/=a[i];
  14.                         t*=a[i];
  15.                 }
  16.                 ret=ret*(t*a[i]-1)/(a[i]-1);
  17.         }
  18.         if (s!=1) return ret*(s+1);
  19.         else return ret;
  20. }
  21. int main()
  22. {
  23.         memset(nprime,false,sizeof(nprime));
  24.         a[0]=0;
  25.         for (i=2;i<=167;i++)
  26.                 if (!nprime[i])
  27.                 {
  28.                         a[++a[0]]=i;
  29.                         for (j=i*i;j<=167;j+=i)
  30.                                 nprime[j]=true;
  31.                 }
  32.         s[0]=0;
  33.         for (i=1;i<=28111;i++)
  34.                 if (calc(i)>(i<<1))
  35.                         s[++s[0]]=i;
  36.         memset(can,false,sizeof(can));
  37.         for (i=1;i<=s[0];i++)
  38.                 for (j=1;j<=s[0];j++)
  39.                         if (s[i]+s[j]>28111) break;
  40.                         else can[s[i]+s[j]]=true;
  41.         for (i=1;i<=28111;i++)
  42.                 if (!can[i]) ans+=i;
  43.         printf("%d\n",ans);
  44.         return 0;
  45. }

 

 

Prject Euler Comments(0) 2009年7月25日 06:08

Project Euler——Problem 22

原题与答案：

Problem 22

19 July 2002

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Answer:871198282

 

分析与解答：

这个问题的题意是给定了一个大概64K的文本name.txt（这个文本的链接给出了，这里就不贴了，太废页面空间了），然后里面是一大堆人的名字，然后我们要做的操作是按照字典序排列后然后对每个名字单词求他的分数，分数的计算是每个字母在大写字母表中的排位的和，然后乘以他的序号，求这些分数的和。本身题目的描述把计算过程都给出了，估计这个题目也没有人会笔算吧（那就是神人了），我们就利用程序直接计算，这里只要注意读入的方式，然后排序计算就可以了，程序员源代码如下：

 

  1. #include<stdio.h>
  2. #include<algorithm>
  3. struct node
  4. {
  5.         char str[15];
  6. };
  7. node name[6000];
  8. int i,j,t,ans;
  9. bool cmp(node s,node t)
  10. {
  11.         return strcmp(s.str,t.str)<0;
  12. }
  13. int main()
  14. {
  15.         freopen("names.txt","r",stdin);
  16.         for (i=0;getchar()=='"';i++)
  17.         {
  18.                 for (j=0;(name[i].str[j]=getchar())!='"';j++);
  19.                 getchar();
  20.                 name[i].str[j]=0;
  21.         }
  22.         std::sort(name,name+i,cmp);
  23.         ans=0;
  24.         for (i=0;name[i].str[0];i++)
  25.         {
  26.                 t=0;
  27.                 for (j=0;name[i].str[j];j++)
  28.                         t+=name[i].str[j]-'A'+1;
  29.                 ans+=t*(i+1);
  30.         }
  31.         printf("%d\n",ans);
  32.         return 0;
  33. }

 

 

Prject Euler Comments(0) 2009年7月22日 05:50

Project Euler——Problem 21

原题与答案：

Problem 21

05 July 2002

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a \neq b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Answer:31626

 

分析与解答：

这个题目的意思是求10000内所有的相亲数的和，所谓的相亲数是指对于一对自然数，如果他们的小于本身的约数的和（不包括本身）等于对方的话，他们称为一对相亲数。这个题目可以通过枚举获得，其实实际上相亲数的数量非常少，首次做这个题的时候我是通过直接到网上查找获得的结果，而如果要写程序实现的话只要枚举10000以内的数值就可以一对对判断了。求所有约数的和可以先将原来的数值分解成如下形式：s=q_1^{t_1}*q_2^{t_2}*...*q_s^{t_s}，实际上获得所有约数的和就是将所有的t_i从0开始到本身进行枚举，然后将所有的枚举情况都加起来。假设其他的指数都不变的情况下，那么就相当于将其他确定的因数构成的元素看成一体当作公约数提取，本身这项就是形成了一个等比数列，因此我们要求的所有约数的和就是\dfrac{q_1^{t_1+1}-1}{q_1-1}*\dfrac{q_2^{t_2+1}-1}{q_2-1}*...*\dfrac{q_s^{t_s+1}-1}{q_s-1}，最后减去本身就是所有小于本身的约数的和了。我的程序源代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. bool nprime[101];
  4. int a[40],i,j,ans,val[10001];
  5. int calc(int s)
  6. {
  7.         int ret=1,t,i;
  8.         for (i=1;i<=a[0]&&s!=1;i++)
  9.         {
  10.                 t=1;
  11.                 while (s%a[i]==0)
  12.                 {
  13.                         s/=a[i];
  14.                         t*=a[i];
  15.                 }
  16.                 ret*=(t*a[i]-1)/(a[i]-1);
  17.         }
  18.         if (s!=1) return ret*(s+1);
  19.         else return ret;
  20. }
  21. int main()
  22. {
  23.         memset(nprime,false,sizeof(nprime));
  24.         a[0]=0;
  25.         for (i=2;i<=100;i++)
  26.                 if (!nprime[i])
  27.                 {
  28.                         a[++a[0]]=i;
  29.                         for (j=i*i;j<=100;j+=i)
  30.                                 nprime[j]=true;
  31.                 }
  32.         ans=0;
  33.         memset(val,-1,sizeof(val));
  34.         for (i=2;i<=10000;i++)
  35.                 if (val[i]==-1)
  36.                 {
  37.                         val[i]=calc(i)-i;
  38.                         if (val[i]<=10000&&val[i]>i)
  39.                         {
  40.                                 val[val[i]]=calc(val[i])-val[i];
  41.                                 if (val[val[i]]==i)
  42.                                 {
  43.                                         ans+=i;
  44.                                         ans+=val[i];
  45.                                 }
  46.                         }
  47.                 }
  48.         printf("%d\n",ans);
  49.         return 0;
  50. }

 

 

Prject Euler Comments(0) 2009年7月22日 05:10

Project Euler——Problem 20

原题与答案：

Problem 20

21 June 2002

n! means n × (n - 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

Answer:648

 

分析与解答：

题目的意思很明朗，是求100!的各位数字之和，啥都不说了，高精度直接计算即可，提及一下位数的估计，因为100!最坏情况下看成是100个100相乘，也就是10^{200}，不超过201位，当然这还是从多计算，实际上小很多，我的代码中是顺手打了个300意思一下，程序源代码如下：

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int a[300],i,j,t,ans;
  4. int main()
  5. {
  6.         memset(a,0,sizeof(a));
  7.         a[0]=a[1]=1;
  8.         for (i=1;i<=100;i++)
  9.         {
  10.                 t=0;
  11.                 for (j=1;j<=a[0];j++)
  12.                 {
  13.                         a[j]=a[j]*i+t;
  14.                         t=a[j]/10;
  15.                         a[j]%=10;
  16.                 }
  17.                 while (t)
  18.                 {
  19.                         a[++a[0]]=t%10;
  20.                         t/=10;
  21.                 }
  22.         }
  23.         ans=0;
  24.         for (i=1;i<=a[0];i++) ans+=a[i];
  25.         printf("%d\n",ans);
  26.         return 0;
  27. }

 

 

Prject Euler Comments(0) 2009年7月21日 05:06