Project Euler number 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); 
} 

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

Это, по существу, что вам нужно.

Попробуйте решить, используя предложенный метод, это поможет вам в решении сложных задач Эйлера.

И ответ проверяется. :)