论坛 › 欧拉计划（Project Euler） › 题目48：找出1^1 + 2^2 + ... + 1000^1000的最后十位

欧拉计划 发表于 2015-5-16 23:38:24

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

Self powers

The series,.

Find the last ten digits of the series, .
题目：



的最后十位是什么？

zhjs 发表于 2015-8-24 13:45:05

运算结果用mathematica验证，结果正确（用C++11标准编写的）！！
结果是：9110846700
(话说怎么加图片啊，我想用图片说明一下，不会上传图片啊，感觉还要输入地址什么的，过程有点麻烦。希望网站管理员弄得简单一点就好啦！！{:1_1:}）
#include<iostream>
using namespace std;
int main()
{
        long long int s=0,a=0;//c++11标准的数据类型
        int i,j;
        for(i=1;i<=1000;++i)
        {
                for(j=1,a=i;j<i;++j)
                {
                        a*=i;
                        if(a>=10000000000) a-=((a/10000000000)*10000000000);//如果超出10位数，就只要这个大数的10位数
                }
                s+=a;
                if(s>=10000000000) s-=((s/10000000000)*10000000000);//超出10位数，就只要这个大数的10位数
               
        }
               
        cout<<"s="<<s<<endl;//最后10位数输出
        return 0;
       
}

迷雾少年 发表于 2016-8-30 22:16:13

9110846700

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

jerryxjr1220 发表于 2016-10-6 10:33:48

9110846700

'''1**1+2**2+...+1000**1000的最后10位'''
total = 0
for i in range(1,1001):
    each = 1
    for j in range(i):
      each *= i
      if len(str(each))>10:
            each = int(str(each)[-10:])
    total += each
    if len(str(total))>10:
      total = int(str(total)[-10:])
print(total)

飘飞的白杨 发表于 2016-10-29 20:28:02

本帖最后由 飘飞的白杨 于 2016-10-29 20:30 编辑

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

愤怒的大头菇 发表于 2016-11-18 20:25:48

for i in range(1,1001):
        count +=i**i
最后10位9110846700

芒果加黄桃 发表于 2017-1-16 13:41:27

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


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

百日维新 发表于 2017-2-28 10:54:18

    public static void main(String[] stra){
    long ret = 0;
      for (int i=1;i <= 1000 ;i++){
         ret += powerfun(i);
         ret =ret % 10000000000l;
      }
      System.out.print(ret);
    }

    private static long powerfun(int i) {
      long ret = 1;
      for (int k = 1; k <= i ;k++){
            ret = ret*i;

            ret =ret % 10000000000l;
      }
      return ret;
    }
    //结果：9110846700

testabc123 发表于 2017-3-14 15:08:36

本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:41 编辑

#!/usr/bin/env python
#coding:utf-8
def Ss():
    num=0
    for i in list(range(1,1001)):
      num+=i**i
    return num

if __name__ == '__main__':
    num=Ss()
    Num=str(num)[-10:]
    print(Num)

渡风 发表于 2017-5-11 00:15:11

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

start = time.clock()
total = 0;
for ii in range(1,1001):
    total = total + ii**ii
   
output = str(total)

L = len(output)

answer = output

print('problem48的答案为：' + str(answer))
over = time.clock()
print ("problem48所耗时间: %f s" % (over - start))

渡风 发表于 2017-6-14 17:53:59

由于matlab 不能做大数计算，所以只能每次计算截取后十位。
效率不是很高。大概两分钟左右的运行时间。
此代码使用matlab编程
Problem48所用时间为130.5419秒
Problem48的答案为9110846700
%% Problem48.m
%最后编辑时间：2017-06-14 17:84 版本1.0
%求1^1 + 2^2 + 3^3 + ...+1000^1000的和的最后十位

% Problem48所用时间为130.5419秒
% Problem48的答案为9110846700


function Output = Problem48()
tic
Total = 0;
for ii = 1000:-1:1
    NowNum = 1;
    for jj = 1:ii
      NowNum = NowNum * ii;
      if length(num2str(NowNum)) > 10
            NumStr = num2str(NowNum);
            NowNum = str2double(NumStr(end-9:end));%取后十位
      end
    end
    disp(ii)
    Total = Total + NowNum;
    if length(num2str(Total)) > 10
      TotalStr = num2str(Total);
      Total = str2double(TotalStr(end-9:end));
    end
end
      
toc
Output = Total;
disp('此代码使用matlab编程')
disp(['Problem48所用时间为',num2str(toc),'秒'])
disp(['Problem48的答案为',num2str(Output)])
end

k往事如烟k 发表于 2019-3-30 01:31:59

9110846700

sum = 0
for i in range(1, 1001):
    sum += i**i

print(int(str(sum)[-10:]))

王小召 发表于 2019-6-24 14:36:27

9110846700print(str(sum())[-10:])

永恒的蓝色梦想 发表于 2019-8-5 18:27:24

本帖最后由 永恒的蓝色梦想 于 2020-5-7 10:20 编辑

快速幂溢出……
C++ 8ms#include<iostream>
using namespace std;


int main() {
    unsigned long long res = 0, temp;
    unsigned short i, j;

    for (i = 1000; i; i--) {
      temp = j = i;

      while (--j) {
            temp = temp * i % 10000000000U;
      }

      res += temp;
    }

    cout << res % 10000000000U << endl;
    return 0;
}

永恒的蓝色梦想 发表于 2019-8-23 16:05:32

本帖最后由 永恒的蓝色梦想 于 2020-8-1 19:52 编辑

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

debuggerzh 发表于 2020-8-1 17:06:57

每步取模
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#define ICRS(i,ini,end) for (int i = ini;i < end;i++)//increase,i.e.ICS(i,0,n)
#define DCRS(i,ini,end) for (int i = ini - 1;i >= end;i--)//decrease,i.e.DCS(i,n,0)
#define MEM(x,y) memset(x,y,sizeof(x))
//#define LOCAL
#define TEST
using namespace std;
typedef long long ll;
const int M = 100 + 10;
const ll INF = 1e10;
const double EPS = 1e-6;
ll x_x(int x){
ll res = 1;
ICRS(i,0,x) {res *= x;res %= INF;}
return res;
}

int main(){
        #ifdef LOCAL
                freopen("i.in","r",stdin);
        #endif // LOCAL
        ll res = 0;
        ICRS(i,1,1000){
    res += x_x(i);
    res %= INF;
        }
        cout << res;
        return 0;
}

a1351468657 发表于 2021-3-21 20:50:06

本帖最后由 a1351468657 于 2021-3-21 20:51 编辑

#include <stdio.h>
#include <string.h>
#include <time.h>


main()
{
        int i, j, k, x, y, z, carry, count, sum = { 0 };
        for (i = 1; i < 1001; i++)
        {
                int a = { 1 };
                carry = 0;
                count = 1;
                for (j = 0; j < i; j++)
                {
                        for (z = 0; z < count; z++)
                        {
                                a = a * i + carry;
                                carry = a / 10;
                                a %= 10;
                               
                        }
                        while (carry)
                        {
                                a = carry % 10;
                                count++;
                                carry /= 10;
                        }
                        y = 0;
                }
               
                for (k = 0; k < j; k++)
                {
                        sum += a + y;
                        y = sum / 10;
                        sum %= 10;
                }
        }
        for (i = 9; i >= 0; i--)
        {
                printf("%d", sum);
        }
}

9110846700

ft215378 发表于 2021-10-22 19:44:14

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

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

guosl 发表于 2022-1-8 15:55:17

本帖最后由 guosl 于 2022-1-8 16:34 编辑

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

int main(void)
{
long long nSum = 0;
mpz_t rop, base, mod;
mpz_inits(rop, base, mod, 0);
mpz_set_ui(mod, 10000000000ll);
for (int i = 1; i <= 1000; ++i)
{
    mpz_set_ui(base, i);
    mpz_powm_ui(rop, base, i, mod);
    nSum += mpz_get_ui(rop);
}
mpz_clears(rop, base, mod, 0);
nSum %= 10000000000ll;
cout << nSum << endl;
return 0;
}
下面是自定义数据类型stBigInt来解决的
/*
答案：9110846700
耗时：0.000315秒
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct stBigInt
{
int a;//每个a保存4位10进制数，故整个新类型可以保存12位10进制数
//三个构造函数
stBigInt(void)
{
    memset(a, 0, sizeof(a));
}
stBigInt(short n)
{
    memset(a, 0, sizeof(a));
    a = n;
}
stBigInt(const stBigInt& b)
{
    memcpy(a, b.a, sizeof(a));
}
//运算符重载
const stBigInt& operator=(const stBigInt& b)//赋值
{
    memcpy(a, b.a, sizeof(a));
    return *this;
}
stBigInt operator+(const stBigInt& b) const //加
{
    int d = 0;//进位
    stBigInt x;
    for (int i = 0; i < 3; ++i)
    {
      d += a + b.a;
      x.a = d % 10000;
      d /= 10000;
    }
    x.a %= 100;//保留10位
    return x;
}
stBigInt operator*(const stBigInt& b) const //乘
{
    stBigInt x;
    for (int i = 0; i < 3; ++i)
    {
      for (int j = 0; j < 3; ++j)
      {
      if (i + j < 3)
          x.a += a * b.a;
      }
    }
    int d = 0;
    for (int i = 0; i < 3; ++i)
    {
      d += x.a;
      x.a = d % 10000;
      d /= 10000;
    }
    x.a %= 100;//保留10位
    return x;
}
//函数
stBigInt qpow(int n)//快速幂
{
    stBigInt x(1);
    if (n == 0)
      return x;
    if (n == 1)
      return *this;
    if ((n & 1) == 0)
    {
      x = qpow(n >> 1);
      x = x * x;
    }
    else
    {
      x = qpow(n - 1);
      x = x * (*this);
    }
    return x;
}
};

int main(void)
{
stBigInt nSum;
for (int i = 1; i <= 1000; ++i)
{
    stBigInt x(i);
    x = x.qpow(i);
    nSum = nSum + x;
}
printf("%d", nSum.a);
printf("%04d", nSum.a);
printf("%04d\n", nSum.a);
return 0;
}

查看完整版本: 题目48：找出1^1 + 2^2 + ... + 1000^1000的最后十位