欧拉计划问题48

Question

以下是问题陈述。

序列 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317。

找出序列 1^1 + 2^2 + 3^3 + ... + 1000^1000 的最后十位数字？

这个问题很简单。 我编写的代码可以正确地找到所有单个数字（即(1^1,2^2,...997^997等，它们都是正确的，因为我用WolframAlpha检查过） :) 当我尝试将所有这些数字相加时，程序总是输出0。 我已经多次阅读了它，但不知道如何找到错误。

PS-由于这里的数字太大，我已将各个数字存储在数组中。 代码

#include<stdio.h>
int n[1001][3001]={};
int sum[3001]={};
int raisedto(int q)
{
    int i,j;    
    //int digit;
    int carry=0;
    int carry1=0;
    n[q][0]=q;
    for(i=0;i<q-1;i++)
    {

    for(j=0;j<3001;j++)
    {
        carry=(q*n[q][j]+carry1)/10;
        n[q][j]=((q*n[q][j])+carry1)%10;
        carry1=carry;
    }
    carry1=0;
    carry=0;
    }
return(0);      
}
int sumof()
{
    int i,j,carry=0,carry1=0;
    for(i=0;i<1001;i=i+2)
    {
        for(j=0;j<3001;j++)
        {
            carry=(n[i][j]+n[i+1][j]+carry1)/10;
            sum[j]=(n[i][j]+n[i+1][j]+carry1)%10;
            carry1=carry;
        }   
        carry1=0;
        carry=0;

    }   
    return(0);
}       
int main(void)
{
    int j,i;
    for(i=0;i<1001;i++)
    {
    printf("%d",i);
    raisedto(i);
    }
    printf("\n");
    sumof();

    for(j=0;j<3001;j++)
    {
        printf("%d",sum[j]);
    }   
    printf("done");
    return(0);
}

- Ole Gooner

---

哇，我简直不敢相信我没想到这个！ 顺便说一句，你能帮我吗？因为我花了一个小时来设计算法和编写代码。 - Ole Gooner

更新1： 我的Sumof函数完全错误。 正在修复中。 - Ole Gooner

您不需要每次取两个，您可以一次对列求和，参见我的答案。 - st0le

我会添加注释，以防万一。 - st0le

你不需要计算所有 n^n 数字，只需它们的最后10位数字。你不需要全部数字来找出 136...377 + 245...789 （每个一百万位数字）组成的值为 ...166。 - ypercubeᵀᴹ

Answer 1

你是正确的，你的 sumof() 函数是错误的...

int sumof()
{
    int i,j,carry=0,s = 0;
    for(i=0;i<3001;i++) //iterate each column (as in digit)
    {
        s = carry;
        for(j=0;j<1000;j++) //sum all the columns  (ie add all units places, then tenths place)
        {
            s+=n[j][i];
        }   
        carry = s / 10; //store carry
        sum[i] = s % 10; //store last digit as the sum
    }   
    return(0);
}       

这基本上就是你所需要的。

尝试使用我建议的方法来解决问题，这将有助于你解决更高级的欧拉问题。

而且答案是正确的。:)

- st0le