Project Euler 16

What is the sum of the digits of the number 2^1000?

//the sum of digits for b^p, in this problem b=2,p=1000
//https://projecteuler.net/problem=16

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int digit[4000];

int main()
{
    int i,j,k,n,m,d,b,p;
    while(cin>>b>>p)
    {
        n=(int)(p*ceil(log(b))); //number of digit in b^p
        memset(digit,0,sizeof(digit));
        digit[0]=1;
        for(i=0;i<p;i++)
        {
            int carry=0;
            for(j=0;j<n;j++)
            {
                int num=digit[j]*b+carry;
                digit[j]=num%10;
                carry=num/10;
            }
        }
        int sum=0;
        for(i=0;i<n;i++)
            sum=sum+digit[i];
        cout<<sum<<endl;
    }
    return 0;
}
Advertisements
About

ACM Competitive Programmer

Posted in Number Theory, Project Euler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: