Project Euler——Problem 16 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 15
Project Euler——Problem 17

Project Euler——Problem 16

daybreakcx posted @ 2009年7月19日 17:41 in Prject Euler , 640 阅读

原题与答案:

Problem 16

03 May 2002

2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^(1000)?

Answer:1366

 

分析与解答:

这个题目题意很直接,就是求2^{1000}各位数的和,直接的做法就是用高精度乘法直接求得结果,然后进行求和,程序也十分容易编写,2^{1000}的位数是log_{10}2^{1000}=302。程序源代码如下所示:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int a[400],i,j,s;
  4. int main()
  5. {
  6.         memset(a,0,sizeof(a));
  7.         a[0]=a[1]=1;
  8.         for (i=1;i<=1000;i++)
  9.         {
  10.                 for (j=1,s=0;j<=a[0];j++)
  11.                 {
  12.                         a[j]=a[j]*2+s;
  13.                         s=a[j]/10;
  14.                         a[j]%=10;
  15.                 }
  16.                 if (s) a[++a[0]]=s;
  17.         }
  18.         for (i=1,s=0;i<=a[0];i++) s+=a[i];
  19.         printf("%d\n",s);
  20.         return 0;
  21. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter