Project Euler

[revin]

http://projecteuler.net/problem

[revin]

Hi can anyone take a look at this problem on euler
http://projecteuler.net/problem=48
My code is below when I stop x at 10 it works fine but trying 1001 gives me the wrong ans, any ideas, help greatly appreciated

#include <iostream>
#include <stdlib.h>
#include <fstream>
using namespace std;



int main()
{
ofstream outfile;
outfile.open("euler#48ans.txt");
long long ans[100000],i,j,k,count,carry,x,y,track=0,manipulate,sum[100000];
for(i=0;i!=100000;i++)
{
sum[i]=0;
}
for(x=1;x!=1001;x++)
{

for(i=0;i!=100000;i++)
{
ans[i]=0;
}

if(x>9)
{
manipulate=x;
while(manipulate>9)
{
ans[track]=manipulate%10;
manipulate=manipulate/10;
track++;
}
ans[track]=manipulate;
}
else if(x<10)
{
ans[0]=x;
}
y=x;
for(count=1;count!=y;count++)
{
carry=0;
for(k=0;k!=100000;k++)
{

i=(ans[k]*x)+carry;
carry=0;
if(i>9)
{
ans[k]=i%10;
carry=i/10;
}
else if(i<10)
{
ans[k]=i;
}
}
}

carry=0;
for(j=0;j!=100000;j++)
{
sum[j]=sum[j]+ans[j]+carry;
carry=0;
if(sum[j]>9)
{
carry=sum[j]/10;
sum[j]=sum[j]%10;
}
}


}
i=0;
cout<<"\nThe sum is :\n";

for(j=99999;j!=-1;j--)
{
if(sum[j]!=0&&i==0)
{
i=1;
}
if (i==1)
{
cout<<sum[j];
}
outfile<<sum[j];
}
outfile.close();
cout<<"\n\n";

return 0;

}

[Athar]

Use code tags to make the code more readable.
And your approach seems to be far too complicated. Since you only need the last 10 digits, you can simply use 64-bit integers and discard the more significant digits.

[Catfish2]

Or you could use a different programming language, which doesn't oppose you.

import std.bigint;
import std.stdio;

BigInt pow(BigInt b, BigInt e)
{
	BigInt r=1;

	while (e-- != 0)
		r *= b;

	return r;
}

void main()
{
	immutable string limit = "1000";
	BigInt n;

	foreach (k; BigInt("1") .. BigInt(limit) + BigInt("1"))
		n += pow(k, k);

	writeln(n.toDecimalString[$-10 .. $]);
}

[revin]

Thnks Athar but even when I discard the more significant digits the last ten digits still seem to be wrong though it works perfectly if I stop x at 10

[Athar]

I tested it and this works fine:

int main()
{
  const uint64_t mod=1e10;
  uint64_t total=0;
  for (int n=1;n<=1000;n++)
  {
    uint64_t pow=n;
    for (int i=1;i<n;i++)
    {
      pow*=n;
      pow%=mod;
    }
    total+=pow;
  }
  total%=mod;
  cout << total << endl;
}

[revin]

Thnks I'll still look over mind to see where I went wrong, but your sollution is much simpler

[revin]

Thnks for the help ppl, especially Athar

[rollie]

Wow...how did I never know about this site?? Very fun problems! So far 14 in, think I may have to break until tomorrow, head starting to hurt.