题目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:}）

#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;
        
}

迷雾少年

9110846700

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

jerryxjr1220

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)

飘飞的白杨

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

愤怒的大头菇

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

最后10位9110846700

芒果加黄桃

# 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算这东西太强了...直接暴力搞..

百日维新

    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

#!/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)

渡风

#此程序是欧拉计划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[L-10:]

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

渡风

由于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

9110846700

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

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

王小召

9110846700

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

永恒的蓝色梦想

快速幂溢出……
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;
}

永恒的蓝色梦想

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

debuggerzh

每步取模

#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

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


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

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/

/*
答案：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[3];//每个a保存4位10进制数，故整个新类型可以保存12位10进制数
  //三个构造函数
  stBigInt(void)
  {
    memset(a, 0, sizeof(a));
  }
  stBigInt(short n)
  {
    memset(a, 0, sizeof(a));
    a[0] = 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[i] + b.a[i];
      x.a[i] = d % 10000;
      d /= 10000;
    }
    x.a[2] %= 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[i + j] += a[i] * b.a[j];
      }
    }
    int d = 0;
    for (int i = 0; i < 3; ++i)
    {
      d += x.a[i];
      x.a[i] = d % 10000;
      d /= 10000;
    }
    x.a[2] %= 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[2]);
  printf("%04d", nSum.a[1]);
  printf("%04d\n", nSum.a[0]);
  return 0;
}