题目48：找出1^1 + 2^2 + ... + 1000^1000的最后十位

欧拉计划

Self powers

The series, .

Find the last ten digits of the series, .

题目：



的最后十位是什么？

zhjs

运算结果用mathematica验证，结果正确（用C++11标准编写的）！！
结果是：9110846700
(话说怎么加图片啊，我想用图片说明一下，不会上传图片啊，感觉还要输入地址什么的，过程有点麻烦。希望网站管理员弄得简单一点就好啦！！{:1_1:}）

1. #include<iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         long long int s=0,a=0;//c++11标准的数据类型
   
6.         int i,j;
   
7.         for(i=1;i<=1000;++i)
   
8.         {
   
9.                 for(j=1,a=i;j<i;++j)
   
10.                 {
    
11.                         a*=i;
    
12.                         if(a>=10000000000) a-=((a/10000000000)*10000000000);//如果超出10位数，就只要这个大数的10位数
    
13.                 }
    
14.                 s+=a;
    
15.                 if(s>=10000000000) s-=((s/10000000000)*10000000000);//超出10位数，就只要这个大数的10位数
    
16.                
    
17.         }
    
18.                
    
19.         cout<<"s="<<s<<endl;//最后10位数输出
    
20.         return 0;
    
21.        
    
22. }

复制代码

迷雾少年

9110846700

楼上厉害，，我是直接最笨办法的。。
我直接算 1+2^2+3^3 + 1000^1000 结果的
1000368199144695177095375011227646795567793680622934654583760988100234910747716194381428659099527845945869942643191290894720342979906407679647259860434238468038326040809691037615370376237713648510063115732951461774246705584266865759601815843666442832284556880313114548151539190975398485496645576513465858582712336401166221956188173449531674102688908321764663020306699770408625340766091595022791379368098369306375602813856646358773751558775213460225796579846583334007349358624342339332981334571237888809283103348760261360175950815609179464026871005243652109980863552142014242903434068560936573231079342194031864413918101238151056509267393515760392842472501391594073463001521843811073767021711026307504695733467897821866906648469828346607412967395801797791683609834722432241952845352564681868240369569566192825555323558078061997527689983848863374786789331581565252059172614339424600986143259233167583371070362625554531852054166117148858229508581589614337594463277554380518380921301218836327102231407332201109740102580216469298331766920619646083790732807627360614428085171565006289728508688964226799647192582924058589530750674578385365561878559589685756225692348914746922810913915619834754117648358035814128670294158565669942087736286390942241547226015004471330630113072042704288905042142628193771918594574302202147201188486345913190833752307476966010547423928871063118783026036381319039052008252072057933666712918946233312793697094074224187872045970976444309242782187738320257490080824330074991698698239561125811127607863900355221737846690567707344074494145266662103839812840216303448476913957072355732716627098372245223046792919747259113157425824064858331415400943278213042954635053574045209984512221264241903550178416824551412548637590007779082539288247751653566899882749594405895102587985539527709493510049546445427265617478399107188238681771215904234119392247489751079085948055945098805617963722928469554263782217625160428008228845552540344494860195267115187092227766195753907211126646150140614744233974765273475619964311852858614167819668340124730487710162006793529985758820653677274379563313495454526632718723482339494825759821076401694316043456512117937935456463521463021197726694983558929132357576188594977516630734212863869456164205525536767311298137182511494649463663073759219213056823561667776093739425742883930712609962163464088038826569132032160692637206183085942987973684584276491784843115472077900401692595694119273553511025991265446039366288921743581333200083717105241171504606883543418862024047552177055263424469501298905901938158245938633694105024815166679813689156668341197713475094389904887126794468901893850475050011205225742455555625750560213230387910337983950333245020653238989115507013882956277763880795687210857196493893142656713105966275422144605988058939600603604226921401402096519294250488670297983396353279460453142375542267881989197481789780678955093763193658603690898474826976906544473978017455720367929981796023041785852626797271283465789498383642350667978127819110846700
用的是库里的大数运算 加法和幂运算

jerryxjr1220

1. 9110846700
   
2. 
   
3. '''1**1+2**2+...+1000**1000的最后10位'''
   
4. total = 0
   
5. for i in range(1,1001):
   
6.     each = 1
   
7.     for j in range(i):
   
8.         each *= i
   
9.         if len(str(each))>10:
   
10.             each = int(str(each)[-10:])
    
11.     total += each
    
12.     if len(str(total))>10:
    
13.         total = int(str(total)[-10:])
    
14. print(total)

复制代码

飘飞的白杨

1. print(sum(i**i for i in range(1,1001))%10**10)

复制代码

愤怒的大头菇

1. for i in range(1,1001):
   
2.         count +=i**i

复制代码

最后10位9110846700

芒果加黄桃

1. # encoding:utf-8
   
2. # 1**1 + 2**2 + 3**3 +......+ 1000**1000 的最后十位是
   
3. from time import time
   
4. def euler048(N=1000):
   
5.     print(sum(i ** i for i in range(1, N + 1)) % 10 ** 10)
   
6. if __name__ == '__main__':
   
7.     start = time()
   
8.     euler048()
   
9.     print('cost %.6f sec' % (time() - start))
   

复制代码

python算这东西太强了...直接暴力搞..

百日维新

1.     public static void main(String[] stra){
   
2.     long ret = 0;
   
3.         for (int i=1;i <= 1000 ;i++){
   
4.            ret += powerfun(i);
   
5.            ret =  ret % 10000000000l;
   
6.         }
   
7.         System.out.print(ret);
   
8.     }
   
9. 
   
10.     private static long powerfun(int i) {
    
11.         long ret = 1;
    
12.         for (int k = 1; k <= i ;k++){
    
13.             ret = ret*i;
    
14. 
    
15.             ret =  ret % 10000000000l;
    
16.         }
    
17.         return ret;
    
18.     }
    
19.     //结果：9110846700

复制代码

testabc123

1. #!/usr/bin/env python
   
2. #coding:utf-8
   
3. def Ss():
   
4.     num=0
   
5.     for i in list(range(1,1001)):
   
6.         num+=i**i
   
7.     return num
   
8. 
   
9. if __name__ == '__main__':
   
10.     num=Ss()
    
11.     Num=str(num)[-10:]
    
12.     print(Num)

复制代码

渡风

#此程序是欧拉计划48题
#找出1^1 + 2^2 + ... + 1000^1000的最后十位
#细节暴力破解

1. import time
   
2. 
   
3. start = time.clock()
   
4. total = 0;
   
5. for ii in range(1,1001):
   
6.     total = total + ii**ii
   
7.    
   
8. output = str(total)
   
9. 
   
10. L = len(output)
    
11. 
    
12. answer = output[L-10:]
    
13. 
    
14. print('problem48的答案为：' + str(answer))
    
15. over = time.clock()
    
16. print ("problem48所耗时间: %f s" % (over - start))

复制代码

渡风

由于matlab 不能做大数计算，所以只能每次计算截取后十位。
效率不是很高。大概两分钟左右的运行时间。
此代码使用matlab编程
Problem48所用时间为130.5419秒
Problem48的答案为9110846700

1. %% Problem48.m
   
2. %最后编辑时间：2017-06-14 17:84 版本1.0
   
3. %求1^1 + 2^2 + 3^3 + ...+1000^1000的和的最后十位
   
4. 
   
5. % Problem48所用时间为130.5419秒
   
6. % Problem48的答案为9110846700
   
7. 
   
8. 
   
9. function Output = Problem48()
   
10. tic
    
11. Total = 0;
    
12. for ii = 1000:-1:1
    
13.     NowNum = 1;
    
14.     for jj = 1:ii
    
15.         NowNum = NowNum * ii;
    
16.         if length(num2str(NowNum)) > 10
    
17.             NumStr = num2str(NowNum);
    
18.             NowNum = str2double(NumStr(end-9:end));%取后十位
    
19.         end
    
20.     end
    
21.     disp(ii)
    
22.     Total = Total + NowNum;
    
23.     if length(num2str(Total)) > 10
    
24.         TotalStr = num2str(Total);
    
25.         Total = str2double(TotalStr(end-9:end));
    
26.     end
    
27. end
    
28.         
    
29. toc
    
30. Output = Total;
    
31. disp('此代码使用matlab编程')
    
32. disp(['Problem48所用时间为',num2str(toc),'秒'])
    
33. disp(['Problem48的答案为',num2str(Output)])
    
34. end
    

复制代码

k往事如烟k

9110846700

1. sum = 0
   
2. for i in range(1, 1001):
   
3.     sum += i**i
   
4. 
   
5. print(int(str(sum)[-10:]))

复制代码

王小召

9110846700

1. print(str(sum([i**i for i in range(1, 1001)]))[-10:])

复制代码

永恒的蓝色梦想

快速幂溢出……
C++ 8ms

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.     unsigned long long res = 0, temp;
   
7.     unsigned short i, j;
   
8. 
   
9.     for (i = 1000; i; i--) {
   
10.         temp = j = i;
    
11. 
    
12.         while (--j) {
    
13.             temp = temp * i % 10000000000U;
    
14.         }
    
15. 
    
16.         res += temp;
    
17.     }
    
18. 
    
19.     cout << res % 10000000000U << endl;
    
20.     return 0;
    
21. }

复制代码

永恒的蓝色梦想

1. print(sum(pow(i, i, 10000000000) for i in range(1, 1001)) % 10000000000)

复制代码

debuggerzh

每步取模

1. #include<sstream>
   
2. #include<iostream>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<cmath>
   
6. #include<ctime>
   
7. #include<cstring>
   
8. #include<string>
   
9. #include<vector>
   
10. #include<set>
    
11. #include<map>
    
12. #include<algorithm>
    
13. #include<queue>
    
14. #include<stack>
    
15. #include<list>
    
16. #define ICRS(i,ini,end) for (int i = ini;i < end;i++)//increase,i.e.ICS(i,0,n)
    
17. #define DCRS(i,ini,end) for (int i = ini - 1;i >= end;i--)//decrease,i.e.DCS(i,n,0)
    
18. #define MEM(x,y) memset(x,y,sizeof(x))
    
19. //#define LOCAL
    
20. #define TEST
    
21. using namespace std;
    
22. typedef long long ll;
    
23. const int M = 100 + 10;
    
24. const ll INF = 1e10;
    
25. const double EPS = 1e-6;
    
26. ll x_x(int x){
    
27.   ll res = 1;
    
28.   ICRS(i,0,x) {res *= x;  res %= INF;}
    
29.   return res;
    
30. }
    
31. 
    
32. int main(){
    
33.         #ifdef LOCAL
    
34.                 freopen("i.in","r",stdin);
    
35.         #endif // LOCAL
    
36.         ll res = 0;
    
37.         ICRS(i,1,1000){
    
38.     res += x_x(i);
    
39.     res %= INF;
    
40.         }
    
41.         cout << res;
    
42.         return 0;
    
43. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <time.h>
   
4. 
   
5. 
   
6. main()
   
7. {
   
8.         int i, j, k, x, y, z, carry, count, sum[3010] = { 0 };
   
9.         for (i = 1; i < 1001; i++)
   
10.         {
    
11.                 int a[3010] = { 1 };
    
12.                 carry = 0;
    
13.                 count = 1;
    
14.                 for (j = 0; j < i; j++)
    
15.                 {
    
16.                         for (z = 0; z < count; z++)
    
17.                         {
    
18.                                 a[z] = a[z] * i + carry;
    
19.                                 carry = a[z] / 10;
    
20.                                 a[z] %= 10;
    
21.                                
    
22.                         }
    
23.                         while (carry)
    
24.                         {
    
25.                                 a[z++] = carry % 10;
    
26.                                 count++;
    
27.                                 carry /= 10;
    
28.                         }
    
29.                         y = 0;
    
30.                 }
    
31.                
    
32.                 for (k = 0; k < j; k++)
    
33.                 {
    
34.                         sum[k] += a[k] + y;
    
35.                         y = sum[k] / 10;
    
36.                         sum[k] %= 10;
    
37.                 }
    
38.         }
    
39.         for (i = 9; i >= 0; i--)
    
40.         {
    
41.                 printf("%d", sum[i]);
    
42.         }
    
43. }

复制代码

9110846700

ft215378

#找出1^1 + 2^2 + ... + 1000^1000的最后十位
result = 0
for num in range(1, 1001):
    result += (num ** num)

print((str(result)[-10:]))

guosl

本题难点在数据的范围，由于求的是最后10位，那么在计算中至少要保留10，但两个10位数的乘，就可能是20位超出了long long的数据范围，所以一般计算机语言中数据类型没有一个可以处理这样长的整数。为此要么借用扩展库要么自己添加自己的扩展数据类型来处理本题。下面我采用两种方式来解决这题。
第一种方式：借用扩展库mpir，具体参考网站：http://www.mpir.org/

1. /*
   
2. 答案：9110846700
   
3. 耗时：0.0007467秒
   
4. */
   
5. #include <iostream>
   
6. #include <mpir.h>
   
7. using namespace std;
   
8. 
   
9. int main(void)
   
10. {
    
11.   long long nSum = 0;
    
12.   mpz_t rop, base, mod;
    
13.   mpz_inits(rop, base, mod, 0);
    
14.   mpz_set_ui(mod, 10000000000ll);
    
15.   for (int i = 1; i <= 1000; ++i)
    
16.   {
    
17.     mpz_set_ui(base, i);
    
18.     mpz_powm_ui(rop, base, i, mod);
    
19.     nSum += mpz_get_ui(rop);
    
20.   }
    
21.   mpz_clears(rop, base, mod, 0);
    
22.   nSum %= 10000000000ll;
    
23.   cout << nSum << endl;
    
24.   return 0;
    
25. }

复制代码

下面是自定义数据类型stBigInt来解决的

1. /*
   
2. 答案：9110846700
   
3. 耗时：0.000315秒
   
4. */
   
5. #include <iostream>
   
6. #include <cstdio>
   
7. #include <cstring>
   
8. using namespace std;
   
9. 
   
10. struct stBigInt
    
11. {
    
12.   int a[3];//每个a保存4位10进制数，故整个新类型可以保存12位10进制数
    
13.   //三个构造函数
    
14.   stBigInt(void)
    
15.   {
    
16.     memset(a, 0, sizeof(a));
    
17.   }
    
18.   stBigInt(short n)
    
19.   {
    
20.     memset(a, 0, sizeof(a));
    
21.     a[0] = n;
    
22.   }
    
23.   stBigInt(const stBigInt& b)
    
24.   {
    
25.     memcpy(a, b.a, sizeof(a));
    
26.   }
    
27.   //运算符重载
    
28.   const stBigInt& operator=(const stBigInt& b)//赋值
    
29.   {
    
30.     memcpy(a, b.a, sizeof(a));
    
31.     return *this;
    
32.   }
    
33.   stBigInt operator+(const stBigInt& b) const //加
    
34.   {
    
35.     int d = 0;//进位
    
36.     stBigInt x;
    
37.     for (int i = 0; i < 3; ++i)
    
38.     {
    
39.       d += a[i] + b.a[i];
    
40.       x.a[i] = d % 10000;
    
41.       d /= 10000;
    
42.     }
    
43.     x.a[2] %= 100;//保留10位
    
44.     return x;
    
45.   }
    
46.   stBigInt operator*(const stBigInt& b) const //乘
    
47.   {
    
48.     stBigInt x;
    
49.     for (int i = 0; i < 3; ++i)
    
50.     {
    
51.       for (int j = 0; j < 3; ++j)
    
52.       {
    
53.         if (i + j < 3)
    
54.           x.a[i + j] += a[i] * b.a[j];
    
55.       }
    
56.     }
    
57.     int d = 0;
    
58.     for (int i = 0; i < 3; ++i)
    
59.     {
    
60.       d += x.a[i];
    
61.       x.a[i] = d % 10000;
    
62.       d /= 10000;
    
63.     }
    
64.     x.a[2] %= 100;//保留10位
    
65.     return x;
    
66.   }
    
67.   //函数
    
68.   stBigInt qpow(int n)//快速幂
    
69.   {
    
70.     stBigInt x(1);
    
71.     if (n == 0)
    
72.       return x;
    
73.     if (n == 1)
    
74.       return *this;
    
75.     if ((n & 1) == 0)
    
76.     {
    
77.       x = qpow(n >> 1);
    
78.       x = x * x;
    
79.     }
    
80.     else
    
81.     {
    
82.       x = qpow(n - 1);
    
83.       x = x * (*this);
    
84.     }
    
85.     return x;
    
86.   }
    
87. };
    
88. 
    
89. int main(void)
    
90. {
    
91.   stBigInt nSum;
    
92.   for (int i = 1; i <= 1000; ++i)
    
93.   {
    
94.     stBigInt x(i);
    
95.     x = x.qpow(i);
    
96.     nSum = nSum + x;
    
97.   }
    
98.   printf("%d", nSum.a[2]);
    
99.   printf("%04d", nSum.a[1]);
    
100.   printf("%04d\n", nSum.a[0]);
     
101.   return 0;
     
102. }

复制代码